문제
https://www.acmicpc.net/problem/1528
문제해설
정말 어려웠던 문제
더 열심히 해야되는것 같다.
결국 내 힘으로 풀지 못하고 풀이를 참고했다.
문제는 1000000이하의 수 n이 주어질 때
4와 7로만 이루어진 수들의 합으로 n을 표현하는 것이다.
처음에는 문제를 잘못 이해해서 4나 7의 합으로만 표현했는데 그게 아니라
예를들어 문제의 예시인 11은 4+7로 표현되고 51은 4+47로 표현된다.
추가 조건은 가능한 적은 갯수의 수로 표현해야하고 갯수가 같다면 사전순으로 앞선 수로 표현해야 한다.
여기서 사전순이란 7+4보다는 4+7로 표현해야 한다는 것이다.
문제풀이
이 문제는 dp풀이도 가능하다고 하지만 bfs를 이용해서 풀었다.
가장 적은 갯수와 사전순의 조건이 있기 때문에 bfs를 이용한 것이다.
문제를 풀면서 새로 알게된 것은 이진수를 이용해 금민수를 구하는 것이다.
금민수를 구해보면 4, 7, 44, 47, 77, 444, 447 ….
이런식으로 나아가는데 4와 7로만 표현되기 때문에 이진수를 이용하면 쉽게 구할 수 있다.
이진수에서 0을 4로 1을 7로 표현해보자
10 -> 4
11 -> 7
100 -> 44
101 -> 47
이런식으로 표현이 가능하다.
왜 맨 앞의 1을 빼는지는 직접해보면 이런식으로 해야만 한다는 것을 알게 될 것이다.
반복문을 이용해 2부터 시작해서 이진수로 수를 바꾸고 다시 금민수로 바꾸는 과정으로 금민수를 구한다.
bfs 과정에서 중요한 부분은
1
2
3
4
5
int next = now + gold[i];
if (visited[next] == -1) {
visited[next] = now;
q.push(next);
}
visited배열에 현재 노드를 저장해야 하는 것이다.
visited[현재 금민수 + 다음 금민수] = 현재 금민수
이렇게 하는 이유는 bfs가 종료되었을 때 어떤 노드들을 거쳐왔는지 출력해야하기 때문이다.
최종적으로 재귀를 이용해 지나왔던 노드들을 출력해주었다.
전체코드
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
queue<int>q;
vector<int>gold;
int visited[1000001];
void trace(int k) {
if (k == 0)
return;
trace(visited[k]);
cout << k - visited[k] << " ";
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
for (int j = 2; j < 200; j++) {
vector<int>bi;
string temp;
int tmp = j;
while (tmp) {
bi.push_back(tmp % 2);
tmp /= 2;
}
for (int i = bi.size() - 1; i >= 0; i--) {
if (i == bi.size() - 1) continue;
if (bi[i] == 0)
temp += "4";
else
temp += "7";
}
gold.push_back(atoi(temp.c_str()));
}
memset(visited, -1, sizeof(visited));
q.push(0);
while (!q.empty()) {
int now = q.front();
q.pop();
if (now == n)
break;
for (int i = 0; i < gold.size(); i++) {
int next = now + gold[i];
if (next > n)
continue;
if (visited[next] == -1) {
visited[next] = now;
q.push(next);
}
}
}
if (visited[n] == -1) {
cout << -1;
return 0;
}
trace(n);
return 0;
}