[구름톤 챌린지] 3주차 학습 일기 #1 (11일차)

문제 링크

구름LEVEL

 

문제 설명

8일 차의 문제와 유사하지만, 이번엔 아이템의 감소 수치가 정해져 있지 않다.

 

 

입력 

• N의 범위는 2부터 10의 6 제곱까지이다.
• 아이템 A, B의 범위는 2 <= A < B <= 13이다.

 

출력

통증을 0으로 만들어주는 아이템의 최소 개수를 출력한다.

 

 

문제 이해

처음엔 이전 통증 문제과 같이 단순 빼기 연산을 이용해서 문제를 풀었었다. 그런데 빼기 연산만을 사용할 경우에는 문제에 있는 예제 중 10000, 4, 13과 같이 0이 나올 수 있는 결과가 있음에도 불구하고 단순 계산으로 0이 나오지 않는 결과가 나오는 것을 확인하였다. 따라서 문제의 풀이 방식을 바꿔야 할 필요가 있다.

 

1. 처음에 주어지는 숫자를 2 x n  + 7 x  m로 나누어 본다.

2. 해당 방식으로 바꿨을 때, 아이템의 최소는 n + m이 될 것이다.

 

n과 m을 각각 0부터 대입해서 답을 도출해보면 이런 결과가 나온다. 

이 부분에서 유추해 볼 수 있는 내용으로는

• 숫자가 2씩 올라갈 때마다 N은 1씩 더해진다.
• 숫자가 7씩 올라갈 때마다 M은 1씩 더해진다.
• 반대로 숫자가 2만큼 내려가면 N은 1을 빼야 한다. (M의 경우도 동일)
• 그렇다면 원하는 숫자 i의 값은 i -2 나 i - 7의 값에 1을 더하면 나올 것이다.
• 원하는 숫자를 뽑기 위해 작은 숫자들의 합으로 나누고( 소문제 ), 이전의 최적의 답이 다음의 최적의 답에 영향을 준다.  => DP를 이용하여 문제를 풀 수 있다.

해당 조건들로 식을 만들어보면 

pain(i) = pain(i - 2) + 1

             or

pain(i) = pain(i - 7) + 1

이라는 식이 도출되고 이를 정리하면 

                 pain(i - A) + 1   (i – A의 이전 연산이 0 이 아닐 때)

pain(i) =         or

                 pain(i - B) + 1   (i – B의 이전 연산이 0 이 아닐 때)

 

의 형식으로 정리해 볼 수 있다.

 

 

 

문제 해결

점화식을 완성한 뒤부터는 문제가 크게 어렵지 않다.

 

원하는 숫자 n이 나올 때까지 A 아이템과 B 아이템에 대해 연산해 주면 된다.

 

 

 

문제 후기

동적 프로그래밍을 떠올리기까지는 시간이 많이 소요되지 않았는데, 점화식을 짜는 과정에서 문제에 해당하는 조건을 설정하는 부분에서 많이 오래 걸렸던 것 같다. 외에도 배열의 크기나 변수 이름 설정 같은 사소한 이슈들로 테스트를 계속 통과하지 못하여 혼란했었던 것 같다.

 

 

 

전체 코드

#include <iostream>
#include <vector>
#define MAX 1000002
int item[MAX];
int A_item;
int B_item;
using namespace std;

void DP(int n){
	item[0] = 0;

	for(int i = A_item; i <= n; i++){
		if(item[i - A_item] != -1){
			item[i] = item[i-A_item] + 1;
			//cout << i << ", " << item[i] << endl;
		}
		if(i >= B_item){
			if(item[i - B_item] != -1){
					item[i] = item[i-B_item] + 1;
					//cout << i << ", " << item[i] << endl;
		  }
		}
	}
}
int main() {
	int n;
	int count = 0;
	cin >> n;
	cin >> A_item >> B_item;
	fill_n(item, n + 1, -1);
        DP(n);
	cout << item[n] << endl;
}