[백준 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좌표에 대해 수행하여, 그 중에서 가장 큰 값을 결과로 출력합니다.

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

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

 

	#include <iostream>
	#include <algorithm>
	#include <cmath>
	#include <cstring>
	using namespace std;
	#define INF 1e12 //무한히 큰 수
	#define MAX_ELEMENTS 200004 //N*M의 최댓값은 200000
	int N, M, D; //입력값 N, M, D
	long long memo[MAX_ELEMENTS]; //memoization에 활용할 array; -INF로 초기화
	long long input[MAX_ELEMENTS]; //입력값을 담을 array
	long long answer = -INF; //답을 담을 long long형 변수
	//array의 index 밖으로 나가는 것을 방지하기 위한 함수
	bool isInBoundary(int curN, int curM) {
	return (0 <= curN && curN < N && 0 <= curM && curM < M);
	}
	long long memoization(int initM) {
	if (initM >= N*M) //범위 밖으로 나가는지 검사
	return -INF;
	int curN = initM / M; //현재 위치의 N값
	int curM = initM % M; //현재 위치의 M값
	if (curN == (N-1))
	return 0; //N번 행에 도달하였음
	if (memo[initM] != -INF)
	return memo[initM]; //이미 탐색하였다면, 다시 탐색하지 않고 값을 반환한다.
	//curN은 아래로만 내려가고, curMM은 0부터 M 사이에 존재하므로, loop 조건을 아래와 같이 한다.
	for (int i = curN; i <= curN + D; i++) {
	for (int j = curM-D; j <= curM + D; j++) {
	//범위 내에 존재하고, 탐색하고자 하는 곳의 N이 시작점보다 크며, 이동 거리 가능한 범위 내에 존재하면,
	if (isInBoundary(i,j) && curN < i && (abs(i-curN) + abs(j-curM)) <= D)
	memo[initM] = max(memo[initM], input[initM]*input[i*M+j] + memoization(i*M+j));
	//메모이제이션 배열의 값은, 현재 값과 새로 계산된 값 (원소의 곱의 합산) 중 큰 것으로 한다.
	}
	}
	return memo[initM];
	}
	int main() {
	for (int i = 0; i < MAX_ELEMENTS; i++)
	memo[i] = -INF;
	cin >> N >> M >> D;
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
	cin >> input[i*M+j];
	}
	}
	//맨 처음 시작점은 N = 0인 위치 중 어디에서나 가능하므로,
	for (int i = 0; i < M; i++)
	answer = max(answer, memoization(i));
	cout << answer;
	return 0;
	}

view raw 17498_폴짝게임.cpp hosted with ❤ by GitHub

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

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

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

CodeTest-StudyGroup/Code-Test-Study