[백준 17498번] 폴짝 게임

난이도: 골드 5

문제 링크: www.acmicpc.net/problem/17498

17498번: 폴짝 게임

문제 17498번: 폴짝 게임

 

어제 풀었으나 시간 제한에 걸려서 실패했던 문제입니다. (링크)

다이나믹 프로그래밍에 대해 알아보고, 메모이제이션 기법을 활용하여 접근하였더니 성공적으로 풀었습니다.

 

메모이제이션 개념을 간단히 설명하자면,

중복적으로 계산이 이루어질 법한 상황에, 계산의 값을 미리 담아 둔 배열을 활용하여,

이미 계산이 이루어진 항목이라면 다시 계산하는 일 없이 저장된 값을 꺼내어 쓰자는 개념입니다.

 

제 접근법은 이러합니다:

1. 문제에서 주어진 최대 크기 (N*M <= 200000) 을 이용하여, 입력 값 array와 메모이제이션 array 두개를 글로벌 변수로 선언합니다.
2. 메모이제이션 array를 -INF로 초기화 합니다. INF는 충분히 큰 값으로, 저는 1e12를 사용하였습니다.
3. 시작점으로부터 도달할 수 있는 범위를 탐색합니다. 값이 -INF라면 탐색하지 않은 것으로 간주하고, 값을 갱신하기 위해 재귀적으로 함수를 호출합니다. 이때 함수는, 두 element의 곱에 재귀함수 결과의 값을 더합니다.
4. 한 번 값이 설정된 메모이제이션 array는, 다시 계산되는 일 없이 그 값을 return하게 됩니다.
5. 위 과정을 N = 0일때의 모든 M좌표에 대해 수행하여, 그 중에서 가장 큰 값을 결과로 출력합니다.

다이나믹 프로그래밍에 익숙하지 않아서 생각보다 헤맸습니다.

이번에 풀어본 문제를 바탕으로, 다음에 비슷한 유형의 문제가 나온다면 바로 메모이제이션을 떠올려서 풀 수 있도록 해야겠습니다.

 

참고한 글은 아래와 같습니다:

• sejinik.tistory.com/146
• 구종만, "프로그래밍 대회에서 배우는 알고리즘 문제해결전략 1", 인사이트. p207~217

*코딩 스터디 그룹을 통해 접한 문제입니다 (7주차 2번 문제). 링크

CodeTest-StudyGroup/Code-Test-Study