문제 이해 단계
https://www.acmicpc.net/problem/14226
14226번: 이모티콘
영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만
www.acmicpc.net
입력으로 S가 주어지고,
S개의 이모티콘을 만드는 게 목표이다.
다음의 3가지 연산만을 사용하여 S개의 이모티콘을 만들어야 한다.
기본적으로 이모티콘 1개는 입력되어 있다.
문제 조건은 아래와 같다.
1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여 넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.
모든 연산은 1초씩 걸리고,
클립보드에 복사하면 이전에 있던 내용은 없어지고 덮어쓰기 된다.
해당 조건일 때, 이모티콘 S개를 만들기 위해
필요한 시간의 최솟값을 구하는 문제
문제 접근 단계
입력으로 주어지는 S는 최대 1000까지 가능하다.
딱히 특이한 점은 없어 보인다.
문제의 조건에서는 클립보드와 화면을 분리해서 보고 있다.
클립보드에 있는 값을
화면에 옮기고 삭제하고 이런 식으로 하고 있다.
게다가 우리가 구해야 하는 것도 걸리는 시간의 최솟값이다.
걸리는 시간의 최솟값
최솟값을 구할 수 있는 로직은 무엇이 있을까?
DP, BFS, 백트래킹, 그리디..
그중에서 이 문제에는 뭘 적용시킬 수 있을까?
일단 DP를 생각했었다.
N = x일 때 최솟값이 정해져 있었으니까..
근데 3번 조건(화면에 있는 이모티콘 중 하나를 삭제한다.)
때문에 안된다..
왜냐하면 S = 4 일 때를 DP [4]라고 하자.
3번 조건 때문에 DP [5-1]도 비교해줘야 하는데,
그러면 DP [4]보다 큰 수를 미리 알아야 한다.
이 때문에 Bottom-up이 안된다..
그래서 해당 방식은 포기했다. DP는 안될 것 같다.
다음으로는 화면과 클립보드 두 개를 나눠서 생각하고 있기 때문에
클립보드와 화면을 가지고 2차원 배열을 만들면 어떨까?
그리고 해당 문제를 맵처럼 생각하고
조건대로 이동시키는 것이다.
이를 BFS처럼 하면 최솟값을 구할 수 있을 것 같다.
그러니까 클립보드에 2개, 화면에 이모티콘이 4개가 있다면
map [2][4] 이런 식으로 하는 것이다.
근데 이렇게 하면 제일 중요한 정보가 빠져있다.
우리가 구해야 하는 시간 정보이다.
그래서 해당 정보도 포함시켜줘야 하기 때문에
이를 구조체로 만들어준다.
즉, 해당 구조체 안에는
"클립보드, 화면, 시간"의 정보들로 구성되어 있는 것이다.
조건에 맞는 BFS 만들기
일단 중복방문을 방지하기 위해 클립보드,
화면의 2차원 배열인 visit [a][b]를 만든다.
여기서
visit [a][b]
=
현재 클립보드에 a개가 저장되어 있고, 화면에 b개가 있을 때이다.
조건 1
화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
해당 조건에서는 기존에 클립보드에 있던 것은 다 사라지고,
화면에 있던 개수가 그대로 클립보드로 들어간다.
만약 현재 클립보드에 a개가 저장되어 있고,
화면에 b개, 시간이 c초 일 때를 {a, b, c}라고 가정한다.
이때, 조건 1을 실행한다면 {b, b, c+1}이 된다.
c+1이 된 이유는 연산을 한번 했기 때문에 1이 더해진 것이다.
만약 화면에 이모티콘이 아무것도 없을 때는 실행하면 안 된다.
조건 2
클립보드에 있는 모든 이모티콘을 화면에 붙여 넣기 한다.
해당 조건일 때는 클립보드에 있는 개수만큼
화면의 개수에 덧붙여주면 된다.
따라서 1번과 같은 조건 {a, b, c}에서
조건 2를 하면 {a, a+b, c+1}이 된다.
조건 3
화면에 있는 이모티콘 중 하나를 삭제한다.
이는 간단하게 화면에
나와있는 이모티콘 하나만 삭제하면 된다.
따라서
{a, b, c} -> {a, b-1, c+1}
이제 이를 문제로 구현하면 된다.
문제 구현 단계
// 정보 담는 구조체
struct Info{
int clip;
int display;
int time;
};
int s;
bool visited[1001][1001] = {false,}; // 방문 체크
int bfs(Info sx){
visited[sx.clip][sx.display] = true;
queue<Info> q;
q.push({sx.clip,sx.display,sx.time});
while(!q.empty()){
int clip = q.front().clip;
int display = q.front().display;
int time = q.front().time;
if(display == s) return time;
q.pop();
// 조건 1,3의 배열 초과를 방지
if(display > 0 && display <= 1000) {
// 조건1
if(!visited[display][display]){
visited[display][display] = true;
q.push({display,display,time+1});
}
// 조건3
else if(!visited[clip][display-1]){
visited[clip][display-1] = true;
q.push({clip,display-1,time+1});
}
}
// 조건2의 배열 초과 방지
if(clip > 0 && display+clip <= 1000) {
//조건2
if(!visited[clip][display+clip]){
visited[clip][display+clip] = true;
q.push({clip,display+clip,time+1});
}
}
}
return 0;
}핵심적인 코드 부분이다.
구조체 정의, 전역변수, BFS 함수 등이 나타나있다.
전체적으로는 일반적인 큐를 사용한 BFS 함수와 같다.
다른 점은 해당 위치의 방문 체크만 해줄 뿐 아니라,
s의 범위가 0 ~ 1000이기 때문에 각 조건일 때
나타날 수 있는 배열 초과를 방지해 주기 위한 예외처리가 들어간다.
그것 외에는 크게 이해하기 어려울 건 없으리라 생각한다.
아이디어를 떠올리기 어려웠던 문제였다.
시행착오
DP로 풀다가 1시간이 훌쩍 지나가버려서
못 풀었던 문제이다.
진짜 100% DP인 줄 알았는데
조건 3 때문에 탈탈 털렸다.
BFS인 줄은 꿈에도 몰랐는데..
이걸 어떻게 BFS라고 생각하지..?
3일 줬어도 못 풀었을 것 같다..
다양성을 잘 생각해봐야 할 것 같다.. ㅠㅠ
생활비..