https://www.acmicpc.net/problem/14916
14916번: 거스름돈
첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.
www.acmicpc.net
이 문제를 보고 나는 수학적으로 풀어야겠다고 생각했다. 물론 dynamic programing (동적계획법)으로도 풀 수 있지만 딱 처음 떠오른것이 수학적으로 푸는것이였다. 어떤 생각을 했냐면 일단 최대한 5원짜리를 쓰고 남은 돈에서 만약 2로 나눴을 때 나머지가 0이 안되면 5원짜리를 한 개 덜 쓴 후 2로 나누어 주도록 반복하여 2로 나눈 나머지가 0이 되도록 하면 쉽게 풀릴거라고 생각했다. 그리고 예외처리로 처음 최대한 5원짜리를 쓰고 점점 5원짜리를 줄여갈건데 이것이 음수가 되면 거슬러 줄 수 없는 것이므로 -1을 출력하게 구현하였다.
전체 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
int main(){
int n;
cin >> n;
int start = n / 5; // 최대한 5원짜리 사용
int remain = (n - start*5) % 2;
while (remain != 0){ // 2원짜리로 나눴을 때 나머지가 0이면
if(start == 0){
cout << -1;
return 0;
} // 거슬러 줄 수 없는 돈 (5원짜리가 음수가 됨)
start -= 1; // 5원짜리 동전 한개 줄임
remain = (n - start*5) % 2; // 5원짜리 동전빼고 나머지를 2원으로 나눠줌
}
cout << start + (n - start * 5) / 2; // 5원짜리 + 2원짜리 개수
return 0;
} |
cs |
---------------------------------------------------------------------------------------------------------------------
2번째 방법은 dynamic programing(동적 계획법을 이용한 방법이다.)
일단 거스름돈의 규칙을 쭉 적어준다. 돈이 0원일 때 몇개 1원일때 쭉쭉 그러면 규칙이 보인다.
직접 해보시면 이제 x원의 거스름돈은 x-5원의 거스름돈 개수 +1인것을 볼 수 있다.
중요한것은 초기값을 잘 적어주어야한다. 초기값을 0원 부터 8원까지 잘 설정해준 후 그 다음 9원 부터는 -5원한 4원의 값을 불러와 계산해주도록 만들어주면 된다.
전체코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
int main(){
int n;
cin >> n;
int dp[100001];
memset(dp, -1, sizeof(dp));
dp[0] = -1;
dp[1] = -1;
dp[2] = 1;
dp[3] = -1;
dp[4] = 2;
dp[5] = 1;
dp[6] = 3;
dp[7] = 2;
dp[8] = 4; // 초기값 정리
for (int i = 9; i <= n;i++){
dp[i] = dp[i - 5] + 1; // 5개 단위로 한 개씩 늘어남
}
cout << dp[n];
return 0;
} //dynamic programming
|
cs |
사용 알고리즘 : dynamic programing(동적계획법)
yea!