문제 URL : https://www.acmicpc.net/problem/12852
12852번: 1로 만들기 2
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.
www.acmicpc.net
문제 접근법 : 문제는 dp라고 되어있지만
저는 bfs를 이용해서 어떻게 만들어졌는지 자신의 부모가 어떤것인지 memo하면서 풀었습니다.
해당값이 x라면 x는 최대 3가지의 노드가 존재할수있는대
3으로 나눠지면 x/3, 2로나눠지면 x/2 , x-1이 0보다 크면 x-1 의 3가지의 자식노드들을 계속해서 가질수있습니다.
그래서 1이 될때까지
만약 12에서 시작했다면
이와같은 모양이나오는데 빨간색 글자는 높이이고, 보라색 글자는 자신의 부모입니다.
부모가 0이라는건 자신이 루트라는 뜻이죠
일때 자신의 부모를 타고 올라가면 12에서 1을만들때 연산은 3까지 필요할것이고
1에서 부모를 타고올라가면 1,2,4, 12 가 나오며 이것을 거꾸로 출력을하면 끝입니다.
소스코드 :
|
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
|
#include<bits/stdc++.h>
using namespace std;
vector<int> check,memo;
int n;
void input() {
cin >> n;
}
void dfs(int cur) {
if (cur == n) {
cout << cur << " ";
return;
}
dfs(memo[cur]);
cout << cur << " ";
}
void solve() {
memo = check = vector<int>(n + 1, -1);
queue<int> q;
q.push(n);
check[n] = 0;
while (!q.empty()) {
int cur = q.front();
q.pop();
if (cur == 1)break;
if (cur % 3 == 0&&check[cur/3]==-1) {
q.push(cur / 3);
check[cur / 3] = check[cur] + 1;
memo[cur / 3] = cur;
}
if (cur % 2 == 0&&check[cur/2]==-1) {
q.push(cur / 2);
check[cur / 2] = check[cur] + 1;
memo[cur / 2] = cur;
}
if (cur - 1 > 0 && check[cur - 1] == -1) {
q.push(cur - 1);
check[cur - 1] = check[cur] + 1;
memo[cur - 1] = cur;
}
}
cout << check[1] << "\n";
dfs(1);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 11952 좀비 (0) | 2022.07.13 |
|---|---|
| 백준 14461 소가 길을 건너간 이유 7 (0) | 2022.07.13 |
| 백준 16637 괄호 추가하기 (0) | 2022.05.17 |
| 백준 17472 다리 만들기 2 (0) | 2022.05.17 |
| 백준 16437 양 구출 작전 (0) | 2022.05.17 |
