문제 URL : www.acmicpc.net/problem/3687
3687번: 성냥개비
각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다.
www.acmicpc.net
문제접근법 : 성냥개비
0 ~ 9 까지 만들때 필요한 성냥개비는
0 ->6개 , 1 -> 2개 , 2 -> 5개 , 3 -> 5개 , 4->4개 , 5->5개 6 -> 6개 , 7 ->3개 8 -> 7개 , 9 -> 6개 입니다.
그런데 최대값을 만들기위해서 생각해보면 최대값이기에 성냥개비를 가작 적게써서 자릿수를 크게 만들면 되기때문에 가장 적게쓰는 값 1일때 2개를 사용하고 7일때 3개를 쓸수있습니다
즉 짝수와 홀수를 분간해서 홀수라면 앞자리에 7을 하나 붙이고 1을 이어서 쓰면되고
짝수일때는 1을 연속적으로 만들면 최대 자리가 나오기때문에 쉽고 100개를 이어붙이기 때문에 10^50까지 나와야하기때문에 string 형으로 써야합니다.
즉 maxdp[i]= "1"+maxdp[i-2] i가 짝수일때
홀수일때는 maxdp[i] = "7"+maxdp[i-3] 입니다.
즉 maxdp[i-2]나 maxdp[i-3]은 1로 연속된 수여야합니다.
그리고 최소값을 만들려면 스스로 써보면 알수있겠지만 규칙이있습니다.
0~9까지 만들수 있는 성냥개비는 2개~ 7개를 통해서 0~9까지 만들수있는데
성냥개비를 이용해서 2개->1 , 3개 ->7 , 4개 ->4 , 5개->2 ,6개->0 , 7개일땐 ->8을 만들어야합니다.
이것을통해서
mindp[i]= min(mindp[i],mindp[i-(2~7)] (i>=8)식이 성립합니다.
저는 mindp값을 22까지 백트래킹으로 찾아서 규칙을 찾았지만 솔직히 찾아서 규칙찾는게 더 받아들이기가 빠르긴합니다. 여러분도 해보길 추천
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
//By 콩순이냉장고
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
int n;
vector<string> v;
string maxdp[101] = { "","","1","7" };
long long mindp[101] = { 0,0,1,7,4,2,0,8,10,18,22,20,28,68,88,108 };
int minnum[10] = { 0,0,1,7,4,2,0,8 };//성냥개비 n개를 이용해서 만들수있는 숫자
void solve() {
for (int i = 4; i <= 100; i++) {
if (i % 2 == 0)
maxdp[i] = "1" + maxdp[i - 2];
else
maxdp[i] = "7" + maxdp[i - 3];
if (i <= 15)
continue;
mindp[i] = 1e16;
for (int j = 2; j <= 7; j++) {
mindp[i] = min(mindp[i], mindp[i - j] * 10L + minnum[j]);//만들수있는 숫자 최소값 이게가장중요
}
}
mindp[6] = 6; //마지막엔 6값은 6으로 만들어야함
int test;
cin >> test;
while (test--) {
cin >> n;
cout << mindp[n] << " " << maxdp[n] << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
}
|
cs |
궁금한점 혹은 모르는점 있으면 논리적인 오류등 무엇이든 상관없으니
댓글은 언제든 환영입니다.
'백준' 카테고리의 다른 글
| 백준 8983 사냥꾼 (1) | 2021.05.14 |
|---|---|
| 백준 20437 문자열 게임2 (0) | 2021.05.05 |
| 백준 17130 토끼가 정보섬에 올라온 이유 (0) | 2021.04.16 |
| 백준 1600 말이 되고픈 원숭이 (0) | 2021.04.05 |
| 백준 2931 가스관 (0) | 2021.04.05 |
