백준 2839번 : 설탕봉지 C++

https://www.acmicpc.net/problem/2839

 

 

 

문제 탐색

입력 : n

n을 3과 5로 최소한의 계산으로 구하는 것이 관건

만약 3과 5로 만들 수 없다면 -1 출력

 

dp를 사용해서 이전 값을 사용해보는 것으로 했습니다.

여러번의 반복 사용을 줄여서~,,,

 

필요한 식

1. 배열 초기화

for (int i = 0; i < 5000; i++)
  {
    dp[i] = -1;
  }

  dp[3] = 1;
  dp[5] = 1;

미리 이렇게 초기화 해두었고, n이 3이상의 값으로 주어지기에 계산하기 편하려고 dp[3] = 1 이렇게 했습니담

 

2. n > 5일 때

n-3 or n-5 를 통해 이전에 구한 값이 있을 때까지 가야합니다.

 

예를 들어 n = 7

dp[7] = dp[3] + dp[4] 이렇게 나눠질 수 있습니다.

dp[4]는 -1의 값을 가지고 있습니다.(3,5로 나타낼 수 없음) => dp[7] = -1이어야합니다.

이렇듯 dp[i-3] 이나 dp[i-5]의 값이 -1인 경우에는 dp[i]도 -1이어야하고,

그외의 값들은 이전에 구한 값을 이용해야합니다.

 

그래서 나누자면

1. dp[i-3] dp[i-5] 모두 -1이 아닌 경우

2. dp[i-3]만 -1이 아닌 경우

3. dp[i-5]만 -1이 아닌 경우

4. 그외

의 경우로 나눌 수 있겠습니다~

for (int i = 6; i <= n; i++)
  {
    if (dp[i - 3] != -1 && dp[i - 5] != -1)
      dp[i] = min(dp[i - 3], dp[i - 5]) + 1;
    else if (dp[i - 3] != -1)
      dp[i] = dp[i - 3] + 1;
    else if (dp[i - 5] != -1)
      dp[i] = dp[i - 5] + 1;
  }

 

최종 코드

#include <iostream>

using namespace std;

int n;

int dp[5001];

int main()
{
  cin >> n;

  for (int i = 0; i < 5000; i++)
  {
    dp[i] = -1;
  }

  dp[3] = 1;
  dp[5] = 1;

  for (int i = 6; i <= n; i++)
  {
    if (dp[i - 3] != -1 && dp[i - 5] != -1)
      dp[i] = min(dp[i - 3], dp[i - 5]) + 1;
    else if (dp[i - 3] != -1)
      dp[i] = dp[i - 3] + 1;
    else if (dp[i - 5] != -1)
      dp[i] = dp[i - 5] + 1;
  }

int answer = dp[n];

cout << answer << endl;

return 0;
}

이렇게 됩니다~~!!!

 

다른 의견 혹은 더 간단하게 구현 할 수 있을지도...고민해보겠습니담!

오늘 학교에서 다이나믹 프로그래밍에 대해 배워서 백준 문제로 다시 익혀보고 있는데, 어휴...아직 속도가 너무 느리네요ㅠㅠㅠ

아자아자 이번주 dp 마스터 해보게씁니다!!