Adding 1s, 2s, and 3s (DP, + 해석)

- Problem : https://www.acmicpc.net/problem/9095

 

1. 문제 해석

내가 시도한 해석)
int(Integer) 4를 표현하기 위해서 1번째, 2번째, 그리고 3번째 합을 더해서 표현할 수 있는 7가지 방법이 다음 아래에 있다. 

 

프로그램은 주어진 정수에 1, 2, 3번째 합으로 몇가지의 방법을 가질 수 있는지 결정해서 써라. 
너는 11보다 작고 정수를 긍정적으로 추정할 수 있다. 

 

input(입력)은 T에 대한 test cases를 포함한다. 테스트 케이스에 포함된 숫자에 T가 작성되어 있다. 다른 테스트 케이스는 한줄에 정수를 포함한다. 

---

영단어)
- determines : 결정하다 

- assume : 추정하다

 

해석포인트)

1. 1s, 2s, 3s => 번째가 아니라. 1,2,3을 의미하는 것임. 번째는 th로 표현 됨.

2. positive : 긍적적 => 수학적으로 해석하면, '양수'라는 의미임

---

 

올바른 해석)

정수 4는 1, 2, 그리고 3의 합으로 다음 7가지 다른 방식으로 표현될 수 있습니다

프로그램을 작성하여 주어진 정수를 1, 2, 3의 합으로 표현할 수 있는 방법의 수를 결정하십시오. 정수는 양수이며 11보다 작다고 가정해도 좋습니다

 

입력은 T개의 테스트 케이스로 구성됩니다. 테스트 케이스의 개수(T)는 입력 파일의 첫 번째 줄에 주어집니다. 그 이후의 각 테스트 케이스는 한 줄에 작성된 하나의 정수로 이루어져 있습니다

 

 

2. 생각해보기(점화식)

N=1이면, 경우의 수 1

N=2이면, 경우의수 (1,1), (2)  = 2

N=3이면, 경우의 수 (1,1,1), (2,1), (1,2), (3) = 4

N=4이면, 경우의 수 (1,1,1,1), (2,1, 1), (2, 2),(1,1,2), (3, 1), (1, 3) = 7

N=5이면, 경우의 수는 N=4일때의 케이스를 보면 (N-1) + (N-2) + (N-3) 가 경우의 수니까, 13이지 않을까(?, 시간을 들인다면 구할 수 있지만 생략하겠습니다)

 

GPT로 케이스를 돌려보았을 때)

 

DP문제를 풀때 경우의 수를 먼저구하고, 거기에서 규칙을 찾아내서 문제를 푸는 방식으로 진행을 했습니다. 

이렇다 보니 경우의 수에서 잘못 구하거나, N의 숫자가 커지는 경우에는 이를 구하는게 너무 힘듭니다. 

 

문제가 뭘까? 

=> 수학적 귀납법 VS 연역법 부분으로 본다면, 제가 시도한 방법은 수학적 귀납법입니다. 

*수학적 귀납법 : 개별적인 사실로 일반적인 결론을 이끌어내는 것.

N=4일때, (N-1) + (N-2) + (N-3)의 값이니까, N=5일때도, 6일때도, N일때도 (N-1) + (N-2) + (N-3) 값이라는 것. 

 

GPT 추천 왈)
" 알고리즘 문제를 풀 때는 연역적 접근으로 문제의 구조를 분석하여 점화식을 먼저 유도하는 것이 가장 중요하며, 귀납적 계산은 그 유도 과정을 돕거나 결과를 확인하는 보조적인 수단으로 생각하시는 것이 좋습니다. "

 

연역법으로 접근하는 방법

*연역법 : 이미 알고 있는 판단을 근거로 새로운 판단을 유도하는 추론

예시 : 사람은 죽는다. (일반적인 명제) -> 나도 사람이다. 그래서 나도 죽는다. 

 

연역법으로 해당 문제를 푼다는 건)

패턴을 찾지 않고도 점화식을 세우는 방법이다. 

이 방법은 "마지막 단계(Last Step)" 원칙에 기반한다. 

 

N에 도달할 수 있는 경우의 수

1) 합의 마지막 숫자가 1인 경우 : N-1

2) 합의 마지막 숫자가 2인 경우 : N-2

3) 합의 마지막 숫자가 3인 경우 : N-3

=> N = (N-1) + (N-2) + (N-3)

 

이 경우의 수로, 결국 N이 어떤 값이든 위의 명제는 항상 성립한다. 

 

 

2. 생각해보기(알고리즘, 시간복잡도)

N개의 데이터중에서 가장 큰 N을 찾아서, N+1까지의 DP 테이블을 만들어서 저장한다.

출력은 케이스만큼 하면 됨.

 

가장 큰 N까지 for문이 한번만 수행함으로, O(N)의 시간복잡도를 가지고, 

N의 최대값은 11보다 작다고 했음으로, 1초안에 충분히 가능하다. 

 

3. 결과 

https://github.com/moonlight-duck/study-algorithms/pull/27/commits/b638cf069a238a9580783113a2633443bf3b8f1d

[민주] DP (+ Greedy) 문제 by min-99 · Pull Request #27 · moonlight-duck/study-algorithms