알고리즘 문제
[C/C++ 백준 14226번] 이모티콘 (Gold 5)
새파란 공대생
2020. 10. 18. 23:29
14226번: 이모티콘
영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만��
www.acmicpc.net
dp로 푸는 것인지는 생각도 안하고, 그냥 BFS로 해결. 사실 BFS라는 것을 몰랐으면 못 풀었을 것 같다. visit배열을 만들어 모든 경우를 만들어 방문해주면 된다.
질문 검색에서 화면에 있는 이모티콘의 수 M의 개수가 클립보드에 있는 이모티콘의 수 S의 개수보다 작을 때에는 수행할 필요가 없는 이유에 대해 자세히 나와있다(www.acmicpc.net/board/view/24279),
#include <cstdio>
#include <queue>
using namespace std;
bool visit[3001][3001];
int main(void){
int S;
scanf("%d", &S);
queue <pair <pair<int, int>, int>> q;
// 1:{화면, 클립보드}, 실행횟수;
q.push({{1, 0}, 0});
visit[1][0] = true;
while(!q.empty()){
int M = q.front().first.first;
int B = q.front().first.second;
int cnt = q.front().second;
if(M==S){
printf("%d", cnt);
break;
}
q.pop();
if(M>=B){
if(!visit[M][M] && M<=3000 && M>=0){
q.push({{M, M}, cnt+1});
visit[M][M] = true;
}
if(!visit[M+B][B] && M+B<=3000 && B>=0){
q.push({{M+B, B}, cnt+1});
visit[M+B][B] = true;
}
if(M!=0 && (M-1<=3000 && B<=3000) && M-1>=0 && B>=0)
if(!visit[M-1][B]){
visit[M-1][B] = true;
q.push({{M-1, B}, cnt+1});
}
}
}
}