[구현] 프로그래머스 COS Pro 1급 종이접기 (Python 파이썬)

💡문제 링크

https://school.programmers.co.kr/learn/courses/11133/lessons/71162

프로그래머스

 

 

💡문제 분석 요약

종이접기를 해서 구할 수 있는 최댓값을 구하는 문제

종이의 크기는 4*4로 고정이고, 각 칸마다 숫자가 적혀있다.

가로 혹은 세로로 접어서 만나는 숫자끼리 합했을 때 나오는 값의 최댓값을 구하는 문제이다.

이 빨간선을 접어서 나오는 숫자는 26, 20, 55, 29이고 이 중에서 가장 큰 수는 55임을 알 수 있다.

 

💡알고리즘 설계

def solution(grid):
    answer = 0
    for i in range(4):
        for j in range(4):
            for k in range(j + 1, 4, 2):
                answer = max(answer, max(grid[i][j] + grid[j][k], grid[j][k] + grid[k][i]))
    return answer

주어진 코드에서 디버깅하는 문제였다.

answer = max(answer, max(grid[i][j] + grid[j][k], grid[j][k] + grid[k][i]))

딱 봐도 많은 변화를 줄 수 있는 이 줄을 고쳐야겠다는 생각이 들었다.

총 세 개의 값 중에서 최댓값을 구하는 것인데, grid[][] 인덱스가 잘못되어 있는 것을 볼 수 있다.

첫 번째 비교값은 answer이고,

두 번째 비교값은 grid[i][j] + grid[j][k]가 아닌 grid[i][j] + grid[i][k]로 두어 세로로 종이를 접었을 때의 경우를 본다.

세 번째 비교값은 grid[j][k] + grid[k][i]가 아닌 grid[k][j] + grid[j][i]로 두어 가로로 종이를 접었을 때의 경우를 본다.

즉, 정사각형의 대칭성을 이용하여 푸는 문제이다.

💡코드

def solution(grid):
    answer = 0
    for i in range(4):
        for j in range(4):
            for k in range(j + 1, 4, 2):
                answer = max(answer, max(grid[i][j] + grid[i][k], grid[j][i] + grid[k][i]))
    return answer

 

💡 오답 풀이

...

 

💡 다른 풀이

...

 

💡 느낀점 or 기억할정보

꽤 까다롭다..