COS PRO 1급 기출문제 소용돌이 수 JAVA 풀이(dp를 이용한 간단한 풀이)
문제
구름HOME
구름은 클라우드 기술을 이용하여 누구나 코딩을 배우고, 실력을 평가하고, 소프트웨어를 개발할 수 있는 클라우드 소프트웨어 생태계입니다.
www.goorm.io
COS PRO 1급 기출문제 중 위 문제가 꽤 재밌어서 가져와봤다.
N*N 격자에 1부터 N까지의 수가 소용돌이 순서로 있을 때 대각선상에 있는 수들의 합을 구하는 문제다.
풀이
처음 이 문제를 봤을 땐 N이 1부터 100까지라고 했으니 최대 100*100 = 10000의 크기이므로 브루트포스로 풀 수 있을 것 같았다.
그러나 2차원 배열에 소용돌이 순서로 숫자를 채워 넣는 코드를 작성하는 건 매우 귀찮아 보였고 출제자가 그런 의도로 문제를 냈을 것 같지 않았다.
그래서 4*4, 5*5 격자를 직접 그려보다 보니 한 가지 규칙이 보이기 시작했다.
그림으로 보면 규칙이 보일 것이다.
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;
}