현재 한 변의 길이가 9 인데 한가지 색깔이 아니다. 한 변 길이가 3이 되도록 9등분 해야 한다. 
 
(0,0)이 왼쪽 위의 좌표라면,  시작점 좌표는 9개가 된다. 길이는 3이다. 
(0,0), (0,3), (0,6)
(3, 0), (3,3) (3, 6)
(6, 0), (6,3) (6, 6)
 
#include <bits/stdc++.h>
using namespace std;

int n;
int arr[3000][3000];
int answer[3];

bool check(int starti, int endj, int size){ // 전부 같은 색깔인지 검사
  int color = arr[starti][endj];
  for(int i = starti; i < (starti+size); i++){
    for(int j = endj; j < (endj+size); j++) {
      if (color != arr[i][j]) return false;
    }
  }
  return true;
}

void div_paper(int x, int y, int len){
  if(check(x, y, len)){ 
    answer[arr[x][y]]++; return;
  }

  int div_len = len / 3; // len == 9, div_len == 3
  for(int i = 0; i <3; i++){
    for(int j = 0; j <3; j++){ // 좌표에 0, 3, 6을 더한 시작점에서 다시 검사한다. 
      div_paper(x + i*div_len, y + j*div_len, div_len);
    }
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  for(int i = 0; i < n; i++){
    for(int j = 0; j <n; j++){
      cin >> arr[i][j]; arr[i][j]++; // 양수로 만들기
    }
  }

  div_paper(0,0,n);
  for(auto c : answer) cout << c << '\n';
  
  return 0;
}
 
728x90
저작자표시 비영리 변경금지

'알고리즘 > 백준' 카테고리의 다른 글

크로아티아 알파벳 백준 2941번 c++  (0) 2022.02.22
통계학 백준 2108번 c++  (0) 2022.02.22
하얀 칸 백준 1100번 c++  (0) 2022.02.21
다이얼 백준 5622번 c++  (0) 2022.02.21
네 번째 점 백준 3009번 c++  (0) 2022.02.21
 
체스 판은 하얀칸과 검정칸이 번갈아가며 색칠되어 있다. 
(0,0)이 하얀칸이라는 조건이 있으니까, 짝수행의 짝수열은 하얀칸이다. 홀수행의 홀수열도 하얀칸이다. 
 
행,열이 둘다 짝수일때 F값인지 검사했다. 
행,열이 둘다 홀수일때 F값인지 검사했다. 
 
#include <bits/stdc++.h>
using namespace std;

char board[10][10];
int answer;

void check(int &h, int &w){
  if(board[h][w] == 'F') answer++;
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  for(int i = 0; i < 8; i++)
    for(int j = 0; j < 8; j++)
      cin >> board[i][j];
    
  for(int i = 0; i < 8; i++){
    for(int j = 0; j < 8; j++){
      if(i % 2 == 0 && j % 2 == 0) check(i, j);
      if(i % 2 == 1 && j % 2 == 1) check(i, j);
    }
  }
  cout << answer;

  return 0;
}
 
 
아래의 성질을 이용했다. 
짝수 + 짝수 == 짝수 
홀수 + 홀수 == 짝수 
#include <bits/stdc++.h>
using namespace std;

string st;
int answer;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  for (int i = 0; i < 8; i++){
    cin >> st;
    for (int j = 0; j < 8; j++) {
      if((i + j) % 2 == 0 && st[j] == 'F') answer++;
    }
  }
  cout << answer;

  return 0;
}
 
 
728x90
저작자표시 비영리 변경금지

'알고리즘 > 백준' 카테고리의 다른 글

통계학 백준 2108번 c++  (0) 2022.02.22
종이의 개수 백준 1780번 c++  (0) 2022.02.21
다이얼 백준 5622번 c++  (0) 2022.02.21
네 번째 점 백준 3009번 c++  (0) 2022.02.21
백설 공주와 일곱 난쟁이 백준 3040번 c++  (0) 2022.02.20

문제 링크 

 

처음에는 문자열의 범위 조건으로 총합을 구했다. 

다른 분의 코드를 보고 문자의 인덱스 자체를 숫자로 쓰는 코드로 바꿔서 다시 풀었다. 

 

 

"맞았습니다" 코드 링크1 

#include <bits/stdc++.h>
using namespace std;

string input;
int len, sum;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> input;
  len = input.size();

  for(int i = 0; i < len; i++){
    char ch = input[i];

    if(ch >= 'W') sum += 10;
    else if(ch >= 'T') sum += 9;
    else if( ch >= 'P') sum += 8;
    else if(ch >= 'M') sum += 7;
    else if(ch >= 'J') sum += 6;
    else if(ch >= 'G') sum += 5;
    else if(ch >= 'D') sum += 4;
    else if(ch >= 'A') sum += 3;
  }
  cout << sum;

  return 0;
}

 

 

"맞았습니다" 코드 링크2 : 문자의 인덱스를 숫자로 활용 

#include <bits/stdc++.h>
using namespace std;

string input;
string numst = "22233344455566677778889999"; // 다이얼 숫자 그대로 사용

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> input;

  int sum = 0;
  int len = input.size();

  for(int i = 0; i < len; i++){
    int numidx = input[i] - 'A';
    sum += (numst[numidx] - '0' + 1); // 다이얼 숫자보다 +1초 더 걸림.
  }
  cout << sum;

  return 0;
}
728x90
저작자표시 비영리 변경금지

'알고리즘 > 백준' 카테고리의 다른 글

종이의 개수 백준 1780번 c++  (0) 2022.02.21
하얀 칸 백준 1100번 c++  (0) 2022.02.21
네 번째 점 백준 3009번 c++  (0) 2022.02.21
백설 공주와 일곱 난쟁이 백준 3040번 c++  (0) 2022.02.20
색종이 만들기 백준 2630번 c++  (0) 2022.02.20
 

문제링크

처음에는 if else 조건문으로 분기해서 풀었다.
다른 분들의 코드를 보니 xor 연산을 하길래 xor 연산을 적용해서 짧은 코드로 다시 풀었다. 
xor은 다르면 1을 출력하니까, 같은 수는 무시하고 다른 수만 남는다. 
(30, 20)
(10, 10)
(10, 20)
3 점을 보면 규칙을 발견할 수 있는데, 하나 남는 수들이 답으로 나와야 한다. 즉, (30, 10) 
따라서  30, 10, 10 중에서 같은 것들은 빼고, ‘다른 수'만 남겨야 하기 때문에 xor 연산을 이용할 수 있다. 
 
#include <bits/stdc++.h>
using namespace std;

int a, b;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  vector<pair<int,int>> v;
  for(int i = 0; i < 3; i++){
    cin >> a >> b;
    v.push_back({a, b});
  }

  if(v[0].first == v[1].first)
    cout << v[2].first << ' ';
  else if(v[1].first == v[2].first)
    cout << v[0].first << ' ';
  else
    cout << v[1].first << ' ';

  if(v[0].second == v[1].second)
    cout << v[2].second << ' ';
  else if(v[1].second == v[2].second)
    cout << v[0].second << ' ';
  else
    cout << v[1].second << ' ';

  return 0;
}
 
 
#include <bits/stdc++.h>
using namespace std;

int a, b, aa, bb;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  cin >> a >> b;
  for(int i = 0; i < 2; i++) {
    cin >> aa >> bb;
    a ^= aa;
    b ^= bb;
  }
  cout << a << ' ' << b;
  return 0;
}
 
728x90
저작자표시 비영리 변경금지

'알고리즘 > 백준' 카테고리의 다른 글

하얀 칸 백준 1100번 c++  (0) 2022.02.21
다이얼 백준 5622번 c++  (0) 2022.02.21
백설 공주와 일곱 난쟁이 백준 3040번 c++  (0) 2022.02.20
색종이 만들기 백준 2630번 c++  (0) 2022.02.20
최소 힙 백준 1927번 c++  (0) 2022.02.19

문제링크 

 

9명 중에 2명을 뽑아야 한다. 

전체 9명의 숫자의 합을 totalsum이라고 구해둔다. 

totalsum - 2명의 숫자를 해야 한다. 2명을 고르려면 이중 반복문 또는 next_permutation 을 쓰면 된다. 

 

크기 9의 배열 2개가 필요하다. 

난쟁이숫자 배열 hat {7, 8, 10, 13, 15, 19, 20, 23, 25}

조합 배열     check  {0, 0, 0, 0, 0, 0, 0, 1, 1}  -> 난쟁이 2개 조합을 골라야하니까 1이 2개 

 

check 배열을 next_permutation() 하면, 1의 위치가 달라진다. 따라서 1의 위치에 해당하는 숫자를 선택하면 된다. 

 

주의 : next_permutation()을 쓸 때, 초기에 배열이 오름차순으로 정렬되어 있어야한다. 

 [불가능]  check  {1, 1, 0, 0, 0, 0, 0, 0, 0} <- 이것이 이미 next_permutation()의 마지막 결과물이기 때문이다. 

 

만약 배열 초기값이 {1, 2, 3} 이라면, next_permutation()의 마지막 결과는 {3, 2, 1}이 된다. 

 

"맞았습니다" 코드링크 

#include <bits/stdc++.h>
using namespace std;

int totalsum;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  vector<int> hat(9);
  vector<int> check(9);
  check[7] = check[8] = 1;

  for(int i = 0; i < 10; i++){
    cin >> hat[i]; totalsum += hat[i];
  }

  do{
    int temp = 0;
    for(int i = 0; i < 9; i++){
      if(check[i])temp += hat[i];
    }
    if((totalsum - temp) == 100){
      for(int i = 0; i < 9; i++){
        if(!check[i]) cout << hat[i] << '\n';
      }
    }
  }while(next_permutation(check.begin(), check.end()));

  return 0;
}
728x90
저작자표시 비영리 변경금지

'알고리즘 > 백준' 카테고리의 다른 글

다이얼 백준 5622번 c++  (0) 2022.02.21
네 번째 점 백준 3009번 c++  (0) 2022.02.21
색종이 만들기 백준 2630번 c++  (0) 2022.02.20
최소 힙 백준 1927번 c++  (0) 2022.02.19
ATM 백준 11399번 c++  (0) 2022.02.19
 
모든 칸을 확인했을 때, 결과는 2가지다. 
칸의 색깔 비교는 첫 칸을 기준으로 한다. 
(0,0) 부터 (3,3)까지 4x4 만큼의 사각형을 확인한다고 가정한다. 한 변의 길이는 4 다. 
 
1) 모든 칸을 확인했을 때 모두 같은색임  -> 첫 칸 색깔에  카운팅++ 하고 끝낸다. 
 
2) 모든 칸을 확인하는데 첫 칸과 다른 색 발견 -> 4의 반토막인 길이 2의 사각형 4개를 탐색한다. 
4개로 쪼개지니까 재귀함수를 4번 돌려야한다. 
 
(0, 0) 부터 2길이만큼 탐색한다. 
(0, 1)부터 2길이만큼 탐색한다. 
(1, 0)부터 2길이만큼 탐색한다. 
(1,1)부터 2길이만큼 탐색한다. 
 
#include <bits/stdc++.h>
using namespace std;

int N, white_cnt, blue_cnt; // 하양 0, 파랑 1 로 표시
int arr[129][129];

void check(int x, int y, int len){ // 행, 열, 한 변 길이

  int color = arr[x][y];
  for(int i = x; i < x+len; i++){ // 행
    for(int j = y; j < y+len; j++){ // 열
      if(color != arr[i][j]){
        check(x, y, len/2);
        check(x, y + len/2, len/2);
        check(x + len/2, y, len/2);
        check(x + len/2, y + len/2, len/2);
        return;
      }
    }
  }
  if(color == 1) blue_cnt++; // 전부 1이었다면 파랑 카운팅 
  else white_cnt++;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> N;

  for(int i = 0; i < N; i++) // 입력 받기
    for(int j = 0; j < N; j++)
      cin >> arr[i][j];

  check(0, 0, N);
  cout << white_cnt << '\n' << blue_cnt; 
  return 0;
}
 
 
728x90
저작자표시 비영리 변경금지

'알고리즘 > 백준' 카테고리의 다른 글

네 번째 점 백준 3009번 c++  (0) 2022.02.21
백설 공주와 일곱 난쟁이 백준 3040번 c++  (0) 2022.02.20
최소 힙 백준 1927번 c++  (0) 2022.02.19
ATM 백준 11399번 c++  (0) 2022.02.19
나는야 포켓몬 마스터 이다솜 백준 1620번 c++  (0) 2022.02.19
 
priority queue을 오름차순으로 만드려면 greater클래스를 넣어준다. 
 greater<int> : 오름차순
 less<int> : 내림차순 
priority_queue<int, vector<int>, greater<int>> pq;
 
#include <bits/stdc++.h>
using namespace std;

int n, input;
priority_queue<int, vector<int>, greater<int>> pq;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  while(n--){
    cin >> input;
    if(pq.empty() && input == 0){
      cout << 0 << '\n';
    }else if(input == 0){
      cout << pq.top() << '\n';
      pq.pop();
    }else{
      pq.push(input);
    }
  }
  return 0;
}
 
728x90
저작자표시 비영리 변경금지

'알고리즘 > 백준' 카테고리의 다른 글

백설 공주와 일곱 난쟁이 백준 3040번 c++  (0) 2022.02.20
색종이 만들기 백준 2630번 c++  (0) 2022.02.20
ATM 백준 11399번 c++  (0) 2022.02.19
나는야 포켓몬 마스터 이다솜 백준 1620번 c++  (0) 2022.02.19
최대 힙 백준 11279번 c++  (0) 2022.02.19

+ Recent posts

티스토리툴바