거스름돈 문제
동전들에 배수관계가 성립할때만 한정.
대부분의 화폐는 1,5,10,25,50 등 딱 떨어지는 수치를 가지고 있기 때문에 그리디로 해결된다.
https://www.acmicpc.net/problem/5585
https://www.acmicpc.net/problem/11047
[https://blog.tomclansys.com/64]
위는 그리디로 되고
[https://mygumi.tistory.com/129] 여기는 dp문제도 준다.
동전1번
[https://www.acmicpc.net/problem/2293] 일단 이거 풀어야 되는데 잘 모르겠다.
음 분할 문제로 생각되서 접근하게 된다. 그래서 자꾸 재귀함수로 분할해 풀려고 한다.
일단 그냥 생각나는 풀이인 완탐으로 했는데 틀렸다.
//
// main.cpp
// algorithm_practice
//
// Created by 김동환 on 2020/04/12.
// Copyright © 2020 김동환. All rights reserved.
//
#include <iostream>
#include <vector>
using namespace std;
int n,k;
int dp[10001] = {0};
int exi[10001] = {0};
vector<int> vec;
int dfs(int m){
int ret= 0;
if(dp[m]){
return dp[m];
}
if( m == 0 ){
return 1;
}
for(int i=0;i<vec.size();i++){
cout << m << " " << vec[i] << "\n";
if( m - vec[i] >= 0){
ret += dfs(m- vec[i]);
}
}
dp[m] = ret;
return ret;
}
int main(){
freopen("input.txt","r", stdin);
cin >> n >> k;
//cout << n << " "<< k << "\n";
for(int i=0;i<n;i++){
int tmp;
cin >> tmp;
vec.push_back(tmp);
//이게 맞나?
exi[tmp] = 1;
}
cout << dfs(5) <<"\n";
return 0;
}
이게 답이 아니긴 하지만, 왜냐면 시간 초과 날듯. 그래도 일단 이걸로 해보고 싶다. 전에 이런 시행 착오 과정을 건너 뛰어서 개당 문제를 내것으로 만들지 못한듯. 그것도 보다 그런 느낌을 받긴 했는데, 이건 조합이 아니라 순열이다. 1,2,1,1,1 과 1,1,2,1,1이 다르게 카운팅 된다.....
일단 내 전략은 일일이 나누어 부분 문제로 풀려는 거?인가 아님 빼서 경우의 수로 풀려는건가... 뭐가 뭐지
내가 사용한 재귀를 통한 접근법이 순열이라 조합이 아님. 조합을 해결해야 한다.
근데 총 합에서 빼서 내려가 0으로 만드는 방식은 순서를 포함할 여지가 다분한거 같다....
그래서 해결책을 생각해 냈다. 이전에 뺀거 보다 더 작은 수를 빼지 않으면 된다. 5를 예시로 하면
11111
1112
122
5 인셈
//
// main.cpp
// algorithm_practice
//
// Created by 김동환 on 2020/04/12.
// Copyright © 2020 김동환. All rights reserved.
//
#include <iostream>
#include <vector>
using namespace std;
int n,k;
int dp[10001] = {0};
int exi[10001] = {0};
vector<int> vec;
int dfs(int m,int prev){
int ret= 0;
if(dp[m]){
return dp[m];
}
if( m == 0 ){
return 1;
}
for(int i=0;i<vec.size();i++){
//cout << m << " " << vec[i] << "\n";
if( m - vec[i] >= 0 && vec[i] >= prev){
ret += dfs(m- vec[i],vec[i]);
}
}
dp[m] = ret;
return ret;
}
int main(){
freopen("input.txt","r", stdin);
cin >> n >> k;
//cout << n << " "<< k << "\n";
for(int i=0;i<n;i++){
int tmp;
cin >> tmp;
vec.push_back(tmp);
//이게 맞나?
exi[tmp] = 1;
}
cout << dfs(5,0) <<"\n";
return 0;
}
그래도 값이 9가 나온다...
dp에 메모이제이션이 잘 못 됬다. 일단 맞게 구한 코드 같다. 최적화를 해보자. 일단 제출하면 시간초과이다.
//
// main.cpp
// algorithm_practice
//
// Created by 김동환 on 2020/04/12.
// Copyright © 2020 김동환. All rights reserved.
//
#include <iostream>
#include <vector>
using namespace std;
int n,k;
int dp[10001] = {0};
int exi[10001] = {0};
vector<int> vec;
int dfs(int m,int prev){
int ret= 0;
/*
if(dp[m]){
cout << dp[m] << "\n";
return dp[m];
}
*/
if( m == 0 ){
// cout << 1 << "\n";
return 1;
}
for(int i=0;i<vec.size();i++){
if( m - vec[i] >= 0 && vec[i] >= prev){
// cout << m << " " << vec[i] << "\n";
ret += dfs(m- vec[i],vec[i]);
}
}
// dp[m] = ret;
return ret;
}
int main(){
freopen("input.txt","r", stdin);
cin >> n >> k;
//cout << n << " "<< k << "\n";
for(int i=0;i<n;i++){
int tmp;
cin >> tmp;
vec.push_back(tmp);
//이게 맞나?
exi[tmp] = 1;
}
cout << dfs(5,0) <<"\n";
return 0;
}
dp가 틀렸던 이유는 4에서 2를 빼서 dp[2]를 구한다 치면, 2가 2로만 되야지 , dp는 오름차순 고려 안해서 1,1과 2로 나뉘어 2가지가 카운팅 된다.;;
그럼 생각나는 해법은 , dp를 이차원으로 해서 m,k 즉 m을 k 이상으로 구하는 법으로 해야 될텐데 그렇게 하자니 dp 사용이 복잡해 진다. k 이상이라 딱 찾기 힘들듯.. 구간에서 가장큰 값 이런식이 될거같다.....
음 위처럼 했는데 시간초과이다.
//
// main.cpp
// algorithm_practice
//
// Created by 김동환 on 2020/04/12.
// Copyright © 2020 김동환. All rights reserved.
//
#include <iostream>
#include <vector>
using namespace std;
int n,k;
int dp[10001][10001] = {0};
vector<int> vec;
int dfs(int m,int prev){
int ret= 0;
if(dp[m][prev]){
//cout << dp[m][prev] << "\n";
return dp[m][prev];
}
if( m == 0 ){
// cout << 1 << "\n";
return 1;
}
for(int i=0;i<vec.size();i++){
if( m - vec[i] >= 0 && vec[i] >= prev){
// cout << m << " " << vec[i] << "\n";
ret += dfs(m- vec[i],vec[i]);
}
}
dp[m][prev] = ret;
return ret;
}
int main(){
freopen("input.txt","r", stdin);
cin >> n >> k;
//cout << n << " "<< k << "\n";
for(int i=0;i<n;i++){
int tmp;
cin >> tmp;
vec.push_back(tmp);
}
cout << dfs(10,0) <<"\n";
return 0;
}
음 근데 어쨌든 완탐은 좀 포기하고 dp로 가능한가.
dp 로 아래 처럼했는데 그럼 순열로 풀린다. 조합으로 풀려야 하는데;
//
// main.cpp
// algorithm_practice
//
// Created by 김동환 on 2020/04/12.
// Copyright © 2020 김동환. All rights reserved.
//
#include <iostream>
#include <vector>
using namespace std;
int n,k;
int dp[10001] = {0};
vector<int> vec;
int main(){
freopen("input.txt","r", stdin);
cin >> n >> k;
//cout << n << " "<< k << "\n";
for(int i=0;i<n;i++){
int tmp;
cin >> tmp;
vec.push_back(tmp);
dp[tmp] = 1;
}
for(int i=1;i<=k;i++){
for(int j=0;j<vec.size();j++){
if(i - vec[j] > 0){
dp[i] += dp[i - vec[j]];
}
}
}
//cout << dfs(10,0) <<"\n";
cout << dp[k] ;
return 0;
}
3을 만든다면 1 에서 2를 더하면 되고 ,즉 1+2
2에서 1을 더하면 되는데 2는 1+1, 2로 구성되어 있어
1+1+1,2+1로 된다.
즉 2+1 입장에서는 이미 1에 2를 더했었어서 1을 더할필요 없음. 왠지 음 그럼 오름 차순이나 내림 차순으로 더하면 될거같은데, 음 되려나?
ㅇㅇ 안된다.
1 = 1 = 1
2 = 1 + 1, 2 = 2
3 = dp[2] + 1 = 2
4 = dp[3] = 2
음 시간 너무 끌어서 풀이를 봤다. [https://sihyungyou.github.io/baekjoon-2293/]
dp[j] = dp[j] (기존 동전 종류를 이용해 j를 만드는 경우의 수) + dp[j- coins[i]] (새 동전 종류를 사용해 j를 만드는 경우의 수)
음 나랑 다른 점은 반복문 순서가 다른거같은데.....음? 초기화도 다르고. 생각한 식은 같은데 왜 다르게 나오지??
idx 0 1 2 3 4 5 6 7 8 9 10 (k)
dp 1 0 0 0 0 0 0 0 0 0 0 (초기화)
dp 1 1 1 1 1 1 1 1 1 1 1 (1만 사용하여 k를 만들 수 있는 경우의 수)
dp 1 1 2 2 3 3 4 4 5 5 6 (1과 2를 사용하여 k를 만들 수 있는 경우의 수)
dp 1 1 2 2 3 4 5 6 7 8 10 (1, 2, 5를 모두 사용하여 k를 만들 수 있는 경우의 수)해설에 dp 변화는 이런데 내꺼도 해보자.
idx 0 1 2 3 4 5 6 7 8 9 10 (k)
dp 0 1 1 0 0 1 0 0 0 0 0 (초기화)
dp 0 1 1 0 0 1 0 0 0 0 0 K = 1
dp 0 1 2 0 0 1 0 0 0 0 0 K = 2
dp 0 1 2 3 0 1 0 0 0 0 0 K = 3
dp 0 1 2 3 5 1 0 0 0 0 0 K = 4
dp 0 1 2 3 5 8 0 0 0 0 0 K = 5
dp 0 1 2 3 5 8 13 0 0 0 0 K = 6
dp 0 1 2 3 5 8 13 21 0 0 0 K = 7
dp 0 1 2 3 5 8 13 21 34 0 0 K = 8
dp 0 1 2 3 5 8 13 21 34 55 0 K = 9
dp 0 1 2 3 5 8 13 21 34 55 89 K = 10
음 128이랑 좀 다르긴한데;; 근데 일단 이렇게만 봐도 값이 엄청 크네 하면서 생각한건데
사용한 동전을 새로운 k에 대해서도 다시 사용해보니까 같은 비용에대해서 이전에 그 동전으로 만든 값이
존재하겠네라는 생각이 들긴한다.
그니까 동전을 재사용 안하는 방법은 오름 차순 이런거 말고, 재귀로 해서 이전 값 보다 큰값만 넣지 않는 이상
총 합으로 오름차순 하지는 못하는거 같음(해보니까)
동전을 한번씩만 사용하는 쪽으로 구현하는게 더 좋은거같다.
3으로 보면 1로 만든걸 dp[1]에서 1 + 2, dp[2]에서 1+1 +1, 2 +1 아 이 빨간 놈이 문제같다. 나중에 1에 2를 더할건데 2가 미리 존재하니까 이게 좀 잘안되네. 내 생각에 그니까 3을 만들때 2를 사용해서 만들건데, 이미 그전에 2를 사용해서 만들어 논게 있어서 문제다 그니까 순열을 피할려면 1을 미리 쭉 깔고 그다음에 2를 이용해 쭉 만들고 하면 1,2,5 순서대로 만들어 질텐데 내 방법은 1,2, 1,2,5, 1,2,5 동전 사용이 계속 누적되서 순열로 된다...1!@#!@#!@#
//
// main.cpp
// algorithm_practice
//
// Created by 김동환 on 2020/04/12.
// Copyright © 2020 김동환. All rights reserved.
//
#include <iostream>
#include <vector>
using namespace std;
int n,k;
int dp[10001] = {0,};
vector<int> vec;
int main(){
//freopen("input.txt","r", stdin);
cin >> n >> k;
//cout << n << " "<< k << "\n";
for(int i=0;i<n;i++){
int tmp;
cin >> tmp;
vec.push_back(tmp);
// dp[tmp] = 1;
}
dp[0] = 1;
for(int i=0;i<vec.size();i++){
for(int j=vec[i];j <= k;j++){
if(j - vec[i] >= 0){
dp[j] += dp[j - vec[i]];
}
}
}
//cout << dfs(10,0) <<"\n";
cout << dp[k] <<"\n";
return 0;
}
음 근데 진짜 중복 생기는건 알겠느데, 두 반복문의 순서를 바꾸니까 답이 다른게 이해가 안된다.;;; 위에 설명함.... 표보고 생각하는게 난거 같아서.
for(int i=0;i<vec.size();i++){
for(int j= 0;j <= k;j++){
if(j - vec[i] >= 0){
dp[j] += dp[j - vec[i]];
}
}
}
for(int j= 0;j <= k;j++){
for(int i=0;i<vec.size();i++){
if(j - vec[i] >= 0){
dp[j] += dp[j - vec[i]];
}
}
}음 먼저 한개 코인씩 더하면 중복해서 더해질 일이 없긴하겠다.
결국 내가 문제를 어느 부분에서 왜 못풀었는지 고민해 봤는데
3원 만들때 1+2, 2+1이 문제인걸 알았고.
내 dp식이 맞다는 확신이 있으면
좀 더 생각해 봤어야 한다. 답을 보지 말걸
내가 생각한 재귀함수 방법은 너무 돌아간 방법이였다.
3원에 대해 1+1+1 과 1+2를 만들려 했어야 했다. 2+1이 생기지 않게하고.
'알고리즘 문제 풀기' 카테고리의 다른 글
| <스위프트&알고리즘> 못풀음, 동전2 2294번 (0) | 2020.04.16 |
|---|---|
| <백준> 2294번 동전2 (0) | 2020.04.16 |
| <부분합 문제?> 다양한 종류의 냅색 문제?부분합?에 대한 이해를 해보자. (0) | 2020.04.08 |
| <백준> 11400번 단절선, 이중 연결 요소. (0) | 2020.04.04 |
| <leet code> Add Two Numbers ,etc/ c++ malloc vs new (0) | 2020.03.12 |