[ C++/cpp ] 백준 (9095 1, 2, 3 더하기) ⭐DP

백준 9095번 1, 2, 3 더하기

(실버 3)

 

문제링크 https://www.acmicpc.net/problem/9095

 

 

(정답 코드)

#include <iostream>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, t;
    int dp[12];
    dp[1]=1; dp[2]=2; dp[3]=4;
    
    cin >> t;
    
    while(t--) {
        cin >> n;
        
        for(int i=4; i<=n; i++) {
            dp[i] = dp[i-3]+dp[i-2]+dp[i-1];
        }
        
        cout << dp[n] << '\n';
    }

    return 0;
}

 

 

📖 풀이

 이전까지의 값들이 뭔가 메모리제이션되면서 중첩되어 최종 답을 구하게 되는 느낌 == 전형적인 dp 문제다.

 

 i-1, i-2, i-3의 값들에 +1, +2, +3만 붙이면 i번째 수를 1,2,3으로 연산해 만들 수 있는 모든 경우의 수를 고려할 수 있게 된다. 따라서 점화식은 매우 간단하게도.. d[i] = d[i-3]+d[i-2]+d[i-1]이다. 초기값 설정해주고 반복문 돌리기만 하면 끝이다.

끄적끄적,, 풀이노트

 

---

 

✨ 내 풀이의 개선점

이 문제에서야 워낙 n이 작으니 상관은 없다만 다른 문제를 풀다가 비슷한 상황이 또 있다면 n이 주어질 때 마다 매번 d[1]부터 d[n]까지 새로 구하는 것 보다 미리 다 구해두는게 효율적이란걸 기억합시다.

 

 

 내 풀이는 n이 들어올때마다 매번 반복문은 돌았는데, 이러면 중복 계산이 발생한다. d[10]까지를 미리 다 구해두고, d[n]을 그냥 바 로 출력해주는 방식이 훨씬 효율적이다. 따라서 아래와 같이 코드 일부를 수정해볼 수 있다.

 

 11보다 작은 수에 대하여 dp 배열을 모두 채워두고,

이후 테스트케이스마다 추가 연산없이 d[n]을 출력만 해주는 식이다.

// d[i] = i를 1, 2, 3의 합으로 나타내는 방법의 수
int d[20];
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  d[1] = 1; d[2] = 2; d[3] = 4;
  for(int i = 4; i < 11; i++)
    d[i] = d[i-1] + d[i-2] + d[i-3];

  int t;
  cin >> t;
  while(t--){
    int n;
    cin >> n;
    cout << d[n] << '\n';
  }
}