[백준] 14226 이모티콘 C++

1. 문제 설명

• 링크 : https://www.acmicpc.net/problem/14226

14226번: 이모티콘

---

2. 풀이 과정

• 문제 해결의 흐름 
  1.  문제 이해를 위해 예제를 직접 풀어보았다. [화면 속 임티 개수][클립보드 속 임티 개수]
     • (1) 입력 : 2 [1][1] -> [2][1]
     • (2) 입력 : 4 [1][1] -> [2][1] -> [2][2] -> [4][2]
     • (3) 입력 : 6 [1][1] -> [2][1] -> [2][2] -> [4][2] -> [6][2]
     • (4) 입력 : 18 [1][1] -> [2][1] -> [2][2] -> [4][2] -> [6][6] -> [12][6] -> [18][6]
  2. ⭐️ 연산 과정을 거치며 이모티콘 개수 S개를 만드는데 걸리는 최소 시간을 구해야 하므로 bfs를 떠올렸다! 
  3. ⭐️  지난번 '2206 벽 부수고 이동하기' 문제와 같이 화면 속 임티 개수만을 기준으로 방문 처리하게 되면 중복이 발생하기에 방문 배열을 2차원 배열로 만들어주었다. visited[화면 속 임티 개수][클립보드 속 임티 개수] (S는 1000 이하의 수이기에 visited[1001][1001]로 선언해주었다)
  4.  이제 남은 건 저장, 붙여넣기, 빼기의 조건을 정확히 명시하는 것이다-!! (사실 이게 문제의 핵심임)
     • (1) 저장 조건 : 현재 화면 속 임티 개수가 S 이하이면 저장하기 (화면 속 임티 개수가 S보다 크다면 굳이 저장할 필요가 없고 -1씩 빼는 것이 가장 최적화된 루트일 것이다)
     • (2) ⭐️⭐️ 붙여넣기 조건 : 일단 문제 조건에 의해 클립보드 속 임티 개수는 0보다 커야 한다. 그리고 붙여넣기(화면 속 임티 개수 + 클립보드 속 임티 개수)했을 때 값이 S보다 커도 될지 안될지 고민해봐야 한다. 다음 두 가지 경우를 비교해보자. 필자는 질문 게시판을 통해 여러 예제를 입력해보았을 때 2번째의 경우가 더욱 효율적이라 생각하여 채택하였다. 물론 1번째의 경우를 해도 정답이 되더라...??!
       • 1번째 경우 : (화면 속 임티 개수 + 클립보드 속 임티 개수)가 S보다 큰 값이 되어 하나하나 -1을 해주는 경우 
       • 2번째 경우 : (화면 속 임티 개수 + 클립보드 속 임티 개수)가 S보다 크기에 저장하지 않고 -1을 해주다가 ((화면 속 임티 개수 + 클립보드 속 임티 개수) == S)가 되는 순간 붙여넣기해주는 경우 
     • (3) 빼기 조건 : S는 0보다 크고 1000 이하인 값이다.

// 1번쨰 경우 조건문 : S 값은 어짜피 1000 이하이기에 이렇게 설정하였다. 
// 1000보다 큰 수가 되어 -1을 해주는 건 절대 효율적인 루트가 아닐 듯하여 기준값을 1000으로 잡았다.
if (cur_clip > 0 && (cur_screen + cur_clip) <= 1000) { 
            if (visited[cur_screen + cur_clip][cur_clip] == 0 && cur_clip != 0 && (cur_screen + cur_clip <= S)){
                q.push(make_pair(cur_screen + cur_clip, cur_clip));
                visited[cur_screen + cur_clip][cur_clip] = visited[cur_screen][cur_clip] + 1;
            }
 }
 
 // 2번쨰 경우 조건문
if (cur_clip > 0 && (cur_screen + cur_clip) <= S) {
            if (visited[cur_screen + cur_clip][cur_clip] == 0 && cur_clip != 0 && (cur_screen + cur_clip <= S)){
                q.push(make_pair(cur_screen + cur_clip, cur_clip));
                visited[cur_screen + cur_clip][cur_clip] = visited[cur_screen][cur_clip] + 1;
            }
 }

• 나의 코드

// 예제 1. 저장 1 1-> 붙 2 1
// 예제 2. 저장 1 1-> 붙 2 1-> 저장 2 2 -> 붙 4 2
// 예제 3. 저장 1 1-> 붙 2 1-> 저장 2 2 -> 붙 4 2 -> 붙 6 2
// 예제 4. 저장 1 1-> 붙 2 1-> 저장 2 2 -> 붙 4 2 -> 붙 6 2 -> 저장 6 6 -> 붙 12 6 -> 붙 18 6

// 언제 저장하고 언제 붙여넣고 언제 빼줘야하는가??
// 1. 언제 빼는가? 현재 screen_val이 S보다 클 때 빼줘야 함.
// 2. 언제 저장하는가?
// 3. 언제 붙여넣기하는가?

#include <iostream>
#include <queue>

using namespace std;

int S;  // 목표 임티 개수
int visited[1001][1001] = {};
queue<pair<int, int> > q;

int bfs() {
    visited[1][0] = 0;  // 처음엔 화면 임티 개수 1, 클립보드 임티 개수 0
    int screen_val = 1;
    int clip_board = 0;
    q.push(make_pair(screen_val, clip_board));
    int result = 0;

    while(!q.empty()) {
        int cur_screen = q.front().first;
        int cur_clip = q.front().second;
        q.pop();

        if (cur_screen == S) {
            result = visited[cur_screen][cur_clip];
            cout << "결과값 : " << cur_screen << " " << cur_clip << endl;
            break;
        }

        // 1. 저장하는 경우 (화면 속 임티 개수가 S보다 크다면 굳이 저장할 필요가 없다)
        if (cur_screen <= S) {
            if (visited[cur_screen][cur_screen] == 0) {
                q.push(make_pair(cur_screen,cur_screen));
                visited[cur_screen][cur_screen] = visited[cur_screen][cur_clip] + 1;
            }
        }

        // 2. 붙여넣기 하는 경우 (클립보드 속 임티 개수는 0보다 커야한다)
        // ⭐️⭐️ (1) (화면 속 임티 개수 + 클립보드 속 임티 개수)가 S보다 큰 값이 되어 하나하나 -1을 해주는 경우
        // ⭐️⭐️ (2) (화면 속 임티 개수 + 클립보드 속 임티 개수)가 S보다 크기에 저장하지 않고 -1을 해주다가 ((화면 속 임티 개수 + 클립보드 속 임티 개수) == S)가 되는 순간 붙여넣기해주는 경우
        // (1)과 (2)의 경우를 비교해봤을 때 (2)의 경우가 더욱 효율적이다!!!!!
        if (cur_clip > 0 && (cur_screen + cur_clip) <= S) {
            if (visited[cur_screen + cur_clip][cur_clip] == 0 && cur_clip != 0 && (cur_screen + cur_clip <= S)){
                q.push(make_pair(cur_screen + cur_clip, cur_clip));
                visited[cur_screen + cur_clip][cur_clip] = visited[cur_screen][cur_clip] + 1;
            }
        }

        // 3. -1하는 경우 (S는 0보다 크고 1000 이하인 값이다)
        if (cur_screen > 0 && cur_screen <= 1000) {
            if (visited[cur_screen - 1][cur_clip] == 0) {
                q.push(make_pair(cur_screen - 1,cur_clip));
                visited[cur_screen - 1][cur_clip] = visited[cur_screen][cur_clip] + 1;
            }
        }


    }

    return result;
}

int main() {
    cin >> S;
    // 1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. (클립보드 임티 개수 = 화면 임티 개수)
    // 2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. (즉 화면 임티 개수 = 화면 임티 개수 + 클립보드 임티 개수)
    // 3. 화면에 있는 이모티콘 중 하나를 삭제한다. (화면에 있는 임티 개수 - 1)

    cout << bfs();

    return 0;
}

 

• 이 문제를 통해 얻어갈 수 있는 것들
  • '2206 벽 부수고 이동하기' 문제와 마찬가지로 방문 배열이 overwrite되는 경우를 항상 신경 써줘야겠다.
  • ⭐️⭐️ 도착점 혹은 특정값까지의 최소 거리, 연산, 시간 등을 물어보는 문제는 bfs로 구현하는 것이 아닌지 의심할 만하다. 
  • 알고리즘 문제에 대해 여러 정답이 있을 수 있다! 효율성이 틀릴 뿐...

---

3. 후기 

 정말 어려운 문제였다 ㅠㅠㅠ... 조건 잡기가 이렇게 빡세다니...