동전 개수 세기

#include <iostream>
#include <string>
using namespace std;

int change;
int tesn[3] = { 10,40,60 };
int minn = 21e8;
void coinn(int num, int changee) {
	cout << changee << " "<< num <<endl;
	
    
    if (changee < 0) return;
	if (minn < num) return;
	if (changee == 0) {
		if (minn > num) {
			minn = num;
		}
	}
	for (int i = 0; i < 3;i++) {
		if (changee - tesn[i] < 0) continue; //원래 return했다가 틀림
		coinn(num + 1, changee - tesn[i]);
		//changee += tesn[i];
	}
}

int main() {
	cin >> change;

	coinn(0, change);
	cout << minn;
}

 입력 80

출력

 

change남은거 쓴 동전 개수

80 0
70 1
60 2
50 3
40 4
30 5
20 6
10 7
0 8
0 5
10 4
0 5
20 3
10 4
0 5
0 3
30 2
20 3
10 4
10 2
0 3
40 1
30 2
20 3
10 4
0 2
20 1
10 2
0 3
답 : 2

ㅋㅋㅋㅋ

 

좀 줄이는 법 없을려나~

사실 60 -> 40-> 10 순으로 배치했으면 짧았을 듯

 

헐 잘못 된거 찾음 

이렇게 썼더니

40-60에서 걸려서 return 해버려가지고 

80
80 0
20 1
40 1
70 1
10 2
30 2
60 2
0 3
20 3
50 3
3

 

3이 나옴;;;

 

return이 아닌 넘기기 continue를 해야함

 

80
80 0
20 1
10 2
0 3
40 1
0 2
30 2
20 3
10 4
0 5
70 1
10 2
0 3
30 2
20 3
10 4
0 5
60 2
0 3
20 3
10 4
0 5
50 3
10 4
0 5
40 4
0 5
30 5
20 6
10 7
0 8
2

 

가운데에 

//if (minn < num) return;

를 주석 해제 해주면

80
80 0
20 1
10 2
0 3
40 1
0 2
30 2
20 3
70 1
10 2
0 3
30 2
20 3
60 2
0 3
20 3
50 3
2

훨씬 짧아짐