[C++] 백준 9095번 1, 2, 3 더하기

처음 이 문제를 봤을 때

n이 작아서 백트래킹으로 문제를 풀려고 시도했다. 시간제한이 1초이므로 1억번의 연산이 가능한데

이 문제는 n이 아무리 커도 1억번을 넘지 않을거라 생각했다.

 

문제풀이

사용한 변수와 메서드

테스트 케이스를 입력받고 정수 n을 입력받으며 backTracking 메서드를 구현했다.

그리고 매 케이스마다 1, 2, 3 합의 개수를 나타내는 output 변수도 만들었다.

 

메인 함수

메인 함수에서는 간단하다. 매 케이스마다 결과값 output 변수를 0으로 초기화하고 backTracking 메서드를 1, 2, 3부터 시작한다.

이렇게 풀면 쉽게 맞출 수 있다.

 

그런데 이 문제는 백트래킹이 아닌 다이나믹 프로그래밍 문제였다.

 

다이나믹 프로그래밍이란?

 

다이나믹 프로그래밍, 동적 계획법은 큰 문제를 작은 문제로 쪼개어서 푸는 방식이다. 작은 문제가 반복이 된다면 이 작은 문제들을 이용해서 큰 문제를 푸는 방식이다. 작은 문제들의 답을 메모해놓고 큰 문제를 풀 때 쓴다. 피보나치 수열을 예로들면 0 + 1 + 1 + 2 + 3 + 5 + 8 + ... 의 방식으로 진행되는데, 결국 F(n)을 구하기 위해선 F(n-1)을 구해야 한다. DP에는 두 가지 방식이 있다. 1. Top Down : 모든 문제를 필요할 때마다 푸는 방식. 재귀함수 2. Bottom Up : 작은 문제들부터 풀고 큰 문제를 푸는 방식. 규칙성을 찾아야 한다. 반복문을 이용. 다이나믹 프로그래밍은 점화식을 사용해서 푼다고 생각하면 된다.

Bottom Up 방식으로 위 문제를 살펴보자

F[1] = 1

F[2] = 2

F[3] = 4

F[4] = 7

F[5] = 13

F[6] = 24

.

.

.

의 규칙으로 이루어져 있다. 즉 규칙을 보면

An = A(n-1) + A(n-2) + A(n-3)임을 알 수 있다.

코드 전문

위 백트래킹 방식과 다른 점은 재귀가 아닌(DP로는 Top Down이 아닌) Bottom Up 방식으로 구현했다는 점이다.

dp배열을 만들어서 최초로 1, 2, 3번째 idx는 초기화를 해준다.

그리고 각 테스트 케이스마다 n을 입력받고 n이 될 때까지 Bottom Up 방식으로 문제를 해결해나간다.

 

재귀함수를 쓴 것과 시간차이는 없다.

 

GitHub - kimyunseok/study-record: my study-record

코드 전문은 위에서 확인 가능하다.