BOJ 14226

07 Apr 2020 • ProblemSolving

이모티콘

문제출처

문제 해석

  • 3가지 연산만을 사용하여 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 문제입니다.
  • 각 연산은 다음과 같습니다.
    1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장합니다.
    2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 합니다.
    3. 화면에 있는 이모티콘 중 하나를 삭제합니다.

설계(10)

  • BFS로 풀이가 가능할 것으로 보여서 구현을 해봤습니다.
  • 현재 이모티콘 개수와 클립보드 개수의 상태를 표현할 2차원 방문처리용 배열이 필요합니다.
  • 다음 3가지 연산에 대해서 큐를 이용하여 탐색합니다.
    1. 클립보드에 복사-> (x,y) =>(x,x)
    2. 붙여넣기 -> (x,y) => (x+y,y)
    3. 삭제 -> (x,y) => (x-1,y)
  • 붙여넣기하는 경우에 x+y가 최대값(1000)을 넘기지 않도록 합니다.
  • 또한, x-1이 0보다 큰 경우만 삭제하도록 합니다.

구현(10)

코드
#include <iostream>
#include <queue>
using namespace std;
#define MAXN 1001
bool visited[MAXN][MAXN];

queue<pair<int,int> > q;
int N;
int bfs(){
    q.push({1,0});
    visited[1][0] = true;
    int cnt = 0;
    while (!q.empty()){
        int q_size = q.size();
        while (q_size--){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            if (x == N) return cnt;
            // 클립보드에 저장하는 경우
            if (!visited[x][x]) {
                visited[x][x] = true;
                q.push({x,x});
            }
            // 붙여넣기 하는 경우
            if (x+y < MAXN && !visited[x+y][y]){
                visited[x+y][y] = true;
                q.push({x+y,y});
            }
            // 삭제하는 경우
            if (x>0 && !visited[x-1][y]){
                visited[x-1][y] = true;
                q.push({x-1,y});
            }
        }
        cnt++;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    cout << bfs()<<"\n";
    return 0;
}
디버깅
제출결과
  • 0 ms

마무리

  • bfs알고리즘 문제였습니다. 또한 DP로도 구현이 가능할 것으로 보입니다. 추후에 DP구현을 추가적으로 해보겠습니다.
 BOJ

Related Posts