https://www.acmicpc.net/problem/1463
동적계획법을 이용해 풀었습니다.
mem[i] = mem[i-1] +1 은 우선 최댓값(?)을 먼저 넣습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | #include <iostream> #include <algorithm> using namespace std; int main(){ int mem[1000001]; int N; cin >> N; mem[1] = 0; for(int i = 2; i <= N; i++){ mem[i] = mem[i-1]+1; if(i%2==0) mem[i] = min(mem[i],mem[i/2]+1); if(i%3==0) mem[i] = min(mem[i],mem[i/3]+1); } cout << mem[N]; return 0; } | cs |
bfs로도 풀 수 있을 거 같아서, bfs로도 한 번 풀어봤습니다.
#include <iostream>#include <queue>#include <algorithm>using namespace std;int bfs(int n) {bool visit[1000001];int idx=n;int count = 0;queue<int> q;q.push(n);while(1) {int size = q.size();for(int i=0; i<size; i++) {idx = q.front();q.pop();if(idx == 1)return count;if(visit[idx-1] == 0) {q.push(idx-1);visit[idx-1] = 1;}if(idx%2 == 0 && visit[idx/2] == 0) {q.push(idx/2);visit[idx/2] = 1;}if(idx%3 == 0 && visit[idx/3] == 0) {q.push(idx/3);visit[idx/3] = 1;}}count++;}}int main(){int n;cin >> n;cout << bfs(n);return 0;}
반응형
'프로그래밍 > 문제풀이' 카테고리의 다른 글
백준 2156(포도주 시식) (0) | 2018.11.03 |
---|---|
백준 1107 (리모컨) (0) | 2018.11.03 |
백준 1652 (누울 자리를 찾아라) (0) | 2018.11.03 |
백준 9095 (1,2,3 더하기) (0) | 2018.10.31 |
백준 3986(좋은 단어) (0) | 2018.10.20 |