[프로그래머스] 종이접기 - Cos Pro 1급

 문제

https://programmers.co.kr/learn/courses/11132/lessons/71152

COS Pro 1급 Java 모의고사 - 종이접기

 

1. 4 x 4 크기인 정사각형 종이가 1 x 1 크기인 격자 칸으로 나누어져 있음

2. 이 종이를 가로축 혹은 세로축에 평행한 격자 선을 따라 한 번 접었을 때, 만나는 격자 칸에 적힌 숫자의 합이 최대일 때

3. 종이를 접을 때는 만나는 격자 칸이 정확히 일치

 

 

예를 들어 다음과 같이 4 x 4 크기인 종이가 있을 때,

- 종이는 점선 중 하나를 따라서 접을 수 있음
- 붉은색 점선을 따라 종이를 접으면 36과 19가 적힌 칸이 정확히 만남
- 두 숫자의 합은 55일 때 최대값

 

 

 해설 및 코드

어느 정도 직감으로 풀어버린 후, 해설을 하려니 꼬여서 하는 정리...

 

정답부터 말하자면

public int solution(int[][] grid) {
    int answer = 0;
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++)
            for(int k = j + 1; k < 4; k += 2)
                answer = Math.max(answer, Math.max(grid[i][j] + grid[i][k], 
                		grid[j][i] + grid[k][i]));
    return answer;
}

이전코드

grid[i][j] + grid[j][k], grid[j][k] + grid[k][i]

 

정답코드

gird[i][j] + grid[i][k], grid[j][i] + grid[k][i]

 

로 변경하면 된다.

 

 

 

해설

 

좌표로 나타내면 위와 같이 그려지는 데, 각 for문의 k는 오른쪽/아래로 가면서 접혔을 때 만나는 곳의 위치를 나타낸다.

그리고 k는 항상 j와의 관계를 나타내므로( k는 j+1이기 때문) j와 k의 관계가 고정이다.

 

따라서 오른쪽 방향은 row 값이 변하지 않아야 하므로 grid[i][j]와 grid[i][k]를 더해줘야 하는 것이고,

아래 방향은 col 값이 변하지 않아야 하므로 grid[j][i]와 grid[k][i]를 더해주는 것이다.

 

머릿속으로 시뮬 돌려봤자 더 꼬이기만 한 듯 싶다ㅠ