[백준 / BOJ] C++ 2041 숫자채우기

2041번: 숫자채우기

 

문제

https://www.acmicpc.net/problem/2041

2041번: 숫자채우기

 

 

풀이

애드 혹 문제인 만큼 다양한 풀이가 있을 수 있다. 내 풀이는 가장 큰 차이부터 줄여나가면서 채우는 것이었다. 예시와 함께 보자.

 

3×3 크기의 배열이라고 하자. 그러면 1부터 12까지의 차이가 모두 존재해야 한다. 가장 먼저 1을 배치하고 큰 차이부터 채울 것이므로 13을 옆에 둔다. 그러면 배열은 아래와 같이 될 것이다.

1 13 ?
?  ?  ?
?  ?  ?

13의 오른쪽에는 차이가 11이 되어야 하므로 2를 둔다.

1 13 2
?  ?  ?
?  ?  ?

여기서부터는 윗칸과 비교를 하며 채웠다. 가장 먼저 1과 차이가 10이 되는 양의 정수인 11을, 13과의 차이가 9가 되는 4를, 2와 차이가 8이 되는 10을 뒀다.

반응형

 1  13   2
11   4  10
 ?    ?   ?

이제 8까지의 차이는 만들었다. 여기서 자세히 보면 두 번째 행의 이웃하는 원소 간 차이는 7과 6이 된다. 위와 같은 방식으로 6, 8, 7을 채우면 배열은 아래와 같이 구성된다.

 1  13   2
11   4  10
 6   8   7

여기서도 마찬가지로 세 번째 행과 두 번째 행 사이에 차이가 5, 4, 3이 되고 세 번째 행간 이웃하는 원소의 차이가 2, 1이 되어 조건을 만족하게 된다. 같은 방식으로 어떤 크기의 배열도 이룰 수 있었다. (노가다로 6개 만들어 봄)

이제 이걸 구현만 해내면 된다. 가장 먼저 눈에 들어온 것은 각 행에서 홀/짝번째 간 규칙이었다. 편의상 0행~N-1행 0열~M-1열로 부르겠다.

 

1. 홀수번째 행의 홀수번째 수는 1씩 증가하고 짝수번째 수는 1씩 감소한다.

2. 짝수번째 행의 홀수번째 수는 1씩 감소하고 짝수번째 수는 1씩 증가한다.

 

편의상 증가하는 수를 a, 감소하는 수를 b라 하면 체스판의 흑백 칸을 채우듯이 a는 증가하며 채워지며, b는 줄어들며 채워진다. 하지만 행이 바뀔 때마다 연속적이지 않았다. 이에 대한 규칙을 또 찾으려 직접 만든 배열들을 분석했고 출력할 때마다 1씩 증가/감소함을 고려했을 때, (열의 수 M ÷ 2)가 증가/감소했다.

 

물론 단순히 저렇게만 증가/감소하진 않고 열의 수 M이 짝수일 때는 a와 b가 번갈아가며 증가량/감소량이 1만큼 작았다. 그래서 일단 a와 b를 각각 M ÷ 2를 증가/감소시키고 M이 짝수인 경우에만 몇 번째 행인지에 따라 a를 1 더 감소시키거나 b를 1 더 증가시켰다. 이렇게 하면 차이가 1부터 2NM - N - M까지 모두 나타나는 배열을 만들 수 있다.

 

배열을 구성하는 방법과 출력을 구현하는 방법이 아예 달라서 이해하기 어려울 수도 있을 것 같다. 다른 사람들의 풀이를 보고 배울 점도 있을 것 같다. 아래 사진은 문제 풀 때 적어본 TC(?)다. 위에 적힌 수는 가장 큰 차이의 크기, 오른쪽에 +,-는 행이 바뀔 때 a와 b의 변화량이다.

 

 

 

코드

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  int a = 1, b = 2 * n * m - n - m + 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if ((i + j) % 2 == 0) {
        cout << a << ' ';
        a++;
      } else {
        cout << b << ' ';
        b--;
      }
    }
    a += m / 2;
    b -= m / 2;
    if (m % 2 == 0) {
      if (i % 2 == 0)
        b++;
      else
        a--;
    }
    cout << '\n';
  }
  return 0;
}