[COS PRO 기출문제] 소용돌이 수 - JAVA

1. 문제

구름HOME

다음과 같이 n x n 크기의 격자에 1부터 n x n까지의 수가 하나씩 있습니다.

이때 수가 다음과 같은 순서로 배치되어있다면 이것을 n-소용돌이 수라고 부릅니다.

소용돌이 수에서 1행 1열부터 n 행 n 열까지 대각선상에 존재하는 수들의 합을 구해야 합니다.

위의 예에서 대각선상에 존재하는 수의 합은 15입니다.
격자의 크기 n이 주어질 때 n-소용돌이 수의 대각선상에 존재하는 수들의 합을 return 하도록 solution 메소드를 완성해주세요.

---

2. 풀이

n=4일 때

1	2	3	4
12	13	14	5
11	16	15	6
10	9	8	7

n=5일때

1	2	3	4	5
16	17	18	19	6
15	24	25	20	7
14	23	22	21	8
13	12	11	10	9

각각 이런 방식으로 전개된다.

정리해서 규칙을 찾아보면 이렇게 정리된다.

n=2일때) 1+3 -> (2)

n=3일때) 1+5+9 -> (4 4)

n=4일때) 1+7+13+15 -> (6 6 2)

n=5일때) 1+9+17+21+25 -> (8 8 4 4)

 

더하는 수 중 1의 바로 다음 수는 (n-1)*2만큼 차이가 난다. 이 차이는 그 다음 수까지 유지한다.

1 + (4*2) = 9

9 + (4*2) = 17

 

네번째 수부터는 두 쌍씩 (n-1)*2에서 4씩 뺀 값만큼 차이난다. (이거보다 더 좋게 말할 수 있을 것 같은데 어렵다.. 한국어 실력이 모자라다 ^_ㅜ)

 

17 + (4*2-4) = 21

21 + (4*2-4) = 25

 

만약 n이 짝수라면 이 방식을 사용했을 때 마지막으로 더한 수 + 2 를 answer에 더해야 한다. 

 

위의 방식을 코드로 정리하면 아래와 같다.(answer += i*3 + prev*2는 answer = answer + i + (answer + i) + i를 정리한 것이다.)

public int solution(int n) {
    int answer = 1;
    int prev = 1;
    for(int i=(n-1)*2;i>=4;i-=4){
        answer += i*3 + prev*2;
        prev += i*2;
    }
		
    if(n%2==0) answer += prev+2;
    return answer;
}