COS PRO 1급 기출문제 소용돌이 수 JAVA 풀이(dp를 이용한 간단한 풀이)

문제

https://edu.goorm.io/learn/lecture/17301/cos-pro-1%EA%B8%89-%EA%B8%B0%EC%B6%9C%EB%AC%B8%EC%A0%9C-java/lesson/839399/1%EC%B0%A8-%EB%AC%B8%EC%A0%9C5-%EC%86%8C%EC%9A%A9%EB%8F%8C%EC%9D%B4-%EC%88%98-java

구름HOME

 

COS PRO 1급 기출문제 중 위 문제가 꽤 재밌어서 가져와봤다. 

 

N*N 격자에 1부터 N까지의 수가 소용돌이 순서로 있을 때 대각선상에 있는 수들의 합을 구하는 문제다.

 

 

풀이

처음 이 문제를 봤을 땐 N이 1부터 100까지라고 했으니 최대 100*100 = 10000의 크기이므로 브루트포스로 풀 수 있을 것 같았다.

 

그러나 2차원 배열에 소용돌이 순서로 숫자를 채워 넣는 코드를 작성하는 건 매우 귀찮아 보였고 출제자가 그런 의도로 문제를 냈을 것 같지 않았다.

 

그래서 4*4, 5*5 격자를 직접 그려보다 보니 한 가지 규칙이 보이기 시작했다.

 

[그림 1] 규칙

 

그림으로 보면 규칙이 보일 것이다.

 

5*5 격자 안에는 3*3 격자가 들어있다. 따라서 미리 3*3 격자의 값 15를 이용할 수 있다. 

 

근데 여기서 3*3 격자가 시작되기 직전 값인 16을 3*3 격자의 대각선 수들에 모두 더해줘야 한다.

 

ex: (1+16) + (2+16) + (3+16)

 

이 16을 구하는 건 쉽다. 사각형의 한 변의 길이인 N을 이용해 N*4를 한 뒤 모서리가 겹치니 4를 빼주면 된다.

 

ex: 5*4-4 = 16

 

그런데 생각해 보면 N*N 격자에는 N개의 대각선 수가 있을 것이다.

 

따라서 안쪽 3*3 격자의 대각선 합은

16*3+(1+5+9) = 63 일 것이다.

 

여기에 바깥쪽 값을 더해주면 되는데, 이것도 쉽다.

1은 무조건 대각선 수에 포함일 것이고, 오른쪽 아래 대각선 수는 변의 길이를 생각하면 N*2-1일 것이다

따라서 N*2-1+1 = N*2이다.

 

이를 종합해 보면, N*N 격자의 대각선 수 합은

 

answer = N*2 + (N*4-4)*(N-2) + (크기가 N-2인 격자의 대각선 수 합)

 

이다.

 

최대한 쉽게 설명해보려고 했는데 생각보다 설명하기가 어려운 듯하다.

 

코드를 보면서 천천히 이해해 보도록 하자.

public int solution(int n) {
        
        int answer = 0;
        if(n == 1) return 1;
        if(n == 2) return 4;
        int[] dp = new int[n+1];
        dp[1] = 1; dp[2] = 4; 
        for(int i=3; i<=n; i++){
            dp[i] = i*2+(i*4-4)*(i-2)+dp[i-2];
        }
        answer =  dp[n];
        return answer;
}