백준 2041 자바 - 숫자채우기 (boj 2041 java)

문제 : boj2041

 

  배열이랑 반복문만 알면 풀 수 있는 순수 아이디어 문제인데도 다이아 티어를 받은 무서운 문제이다. 별다른 알고리즘적 지식이 필요하지 않으므로 풀기 전에 이 글을 보면 얻어갈 수 있는건 아이디어 뿐이다. 따라서 밑으로 내려 풀이를 보자마자 스포가 되므로, 최대한 스스로 풀어보고 풀이를 보는걸 추천한다(하지만 스스로 풀어봤다면 더이상 풀이가 필요없지)

 

  백준1187번을 같이 풀었던 선배같은 후배와 같이 풀었다. 1187때는 결국 난 못풀었고 후배의 도움으로 풀 수 있었지만 이번엔 내가 먼저 풀이를 찾았다. 기분 좋다.

 

 

 

----- 풀이 스포주의 -----

 

 

 

 

 

  내 경우엔 여러 방식으로 해보다가, 결국 해답을 찾은 키 아이디어는 배열에 어떤 수가 들어갈지 고민하기 보다, 차이를 어떻게 배치할지 고민하기 시작하면서 금방 찾아졌다. 즉 아래 이미지 같이 각 칸에 뭐가 들어갈지 보다는, 각 칸 사이의 차이를 어떻게 설정해야 각 칸에 그 차이만큼의 숫자를 알맞게 넣을 수 있는지 고민하기 시작하면서 풀이가 보였다(이렇게 놓고 보니 배열의 각 칸 사이에 끼어 있는 변의 개수가 2NM-N-M임도 알 수 있었다.).

 

  결론적으로 다음 이미지 한장으로 풀이는 끝이다.

  우측 아래로 대각선으로 진행하면서, 수직으로 좌측하단에서 우측상단으로 진행과 우측상단에서 좌측하단으로 진행을 번갈아가면서 순서대로 각 칸 사이의 차이를 쓰면 된다. 그리고 좌측상단에 1을 넣고 시작하면 항상 저 차이만큼 배열에 숫자를 쓰는게 가능하며, N=1000, M=1000 일때도 2x10^9 이내로 가능하다(이 경우 가장 우측하단은 1,996,003,000 이 나온다.). N=3, M=3일 경우 결과는 다음과 같다.

  n=3, m=1과 같을 때도 마찬가지다. 동일한 로직을 적용할 수 있다.

 

  그럼 이걸 구현만 해주면 된다. 간단히 보자면, 대각선으로 지그재그 순서로 방문하면서 좌측 하단으로 진행 중일 때는 자신의 우측, 아래 순서로 차이를 기입하고 / 우측 상단으로 진행 중일 때는 자신의 아래, 우측 순서로 자기자신에서 차이만큼 더한 값을 작성해주면 된다. 예를들어 n=4, m=3 인 경우의 전체 과정을 그려보면 다음과 같다. 파란색이 현재 보고 있는 값이다.

 

  코드로 구현하면 아래와 같다. swt가 true 일 땐 좌측하단에서 우측상단으로 진행, false일 땐 우측상단에서 좌측하단으로 진행하는 경우이다.

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] arr = new int[n][m];
        arr[0][0] = 1;
        int r = 0;
        int c = 0;
        boolean swt = true;
        int gap = 1;
        while (r!=n-1 || c!=m-1) {
            while (r>=0&&r<n&&c>=0&&c<m) {
                if (swt) {
                    if (r+1<n) arr[r+1][c] = arr[r][c]+gap++;
                    if (c+1<m) arr[r][c+1] = arr[r][c]+gap++;
                    if (r-1<0 || c+1>=m) {
                        if (c+1<m) c++;
                        else if (r+1<n) r++;
                        break;
                    }
                    r--;
                    c++;
                } else {
                    if (c+1<m) arr[r][c+1] = arr[r][c]+gap++;
                    if (r+1<n) arr[r+1][c] = arr[r][c]+gap++;
                    if (r+1>=n || c-1<0) {
                        if (r+1<n) r++;
                        else if (c+1<m) c++;
                        break;
                    }
                    r++;
                    c--;
                }
            }
            swt = !swt;
        }
        StringBuilder answer = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                answer.append(arr[i][j]);
                if (j==m-1) answer.append('\n');
                else answer.append(' ');
            }
        }
        System.out.print(answer);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}