[Python]알고리즘/백준
[그리디 알고리즘] ★ 2873번 - 롤러코스터
[백준] 2873번 - 롤러코스터 풀이 시간: 6~7 시간 1) 문제 해결 아이디어 아이디어를 떠올리는데 어려움을 겪은 문제다. 케이스를 분류하고 일반화하기가 까다로운 문제로 지금까지 풀었던 그리디 문제 중에는 제일 어려운 문제인 것 같다. 특히나 r, c가 모두 짝수인 경우가 구현하기 가장 까다롭기 때문에 푸는데 실패를 계속 겪고 정답이 되기까지 시간이 오래걸렸다. 각 칸은 한 번만 방문할 수 있고 지나간 칸의 합이 가장 최대가 되는경로를 출력하는 문제다. 지나간 칸의 합이 가장 최대가 되기 위해서는 최대한 많은 칸을 지나가야한다. 이 문제는 r, c가 짝수인지 홀수인지에 따라서 케이스를 분리하는 것이 중요 포인트다. 3번째 케이스같은 경우는 제외할 1칸을 어떻게 설정할지를 떠올리는 것이 중요하다. 그..
