Gidhub BE Developer

[BOJ] 14226. 이모티콘

2018-09-22
goodGid

Problem

Problem URL : 이모티콘


[1] Answer Code (18. 09. 22)

#include <iostream>
#include <queue>
#include <string>
#define p pair<int,int>
using namespace std;

int visit[1001][1001];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    // 현재 이모티콘수, 클립보드 복사된 값, 시간
    queue< pair< pair<int,int> , int > > q;
    q.push({ {1,1},1} );
    
    while (! q.empty()) {
        int a = q.front().first.first;
        int b = q.front().first.second;
        int c = q.front().second;
        q.pop();
        
        if( a == n ){
            cout << c << endl;
            break;
        }
        
        visit[a][b] = 1;
        q.push({p(a,a),c+1});
        if(a+b <= 1000 && ! visit[a+b][a+b])
            q.push({p(a+b,b),c+1});
        if(a-1 > -1 && ! visit[a-1][a-1])
            q.push({p(a-1,b),c+1});
    }
    return 0;
}

Review

  • 핵심은 visit[현재 이모티콘의 수][클립보드에 복사된 값]을 신경써줘야한다.

  • 처음엔 visit[a] = 1;처럼 단순히 현재 이모티콘 수로만 중복방문을 체크했더니 틀렸다.

  • 왜냐하면 현재 이모티콘의 수가 같더라도 클립보드에 들어있는 내용에 따라 그 이후 값이 달라질 수 있기 때문이다.

  • 즉 현재 글자뿐아니라 클립보드에 복사된 값까지 고려해줘야한다.


Comments

Content