[BOJ/C++] 1515 - 수 이어 쓰기

https://www.acmicpc.net/problem/1515

1515번: 수 이어 쓰기

---

그리디 공부하다가 찾은 괜찮은 문제

 

되게 복잡하게 생각했었다가... 결국 못풀고 다른 사람 풀이를 찾아봤다.

 

우선 뭔가 규칙이 있을 것이라고 생각했다.

8개의 예제들을 보면 입력의 맨 오른쪽 자리와 출력의 맨 오른쪽 자리가 같았다. (예제2번 제외)

뭔가 숫자의 오름차순?과 관련이 있을것 같아서.. 규칙을 어떻게든 찾아보면 되겠구나..했는데

아무리 고민해도 안나오길래 결국.. 포기했다..

 

그냥 단순하게 모든 숫자에 대해서 브루트포스를 돌려도 풀리는 문제였던걸로..

브루트포스가 안될거라고 생각했던게, 문제에서 N값의 범위가 안주어져있다.

N의 범위대신 입력되는 string의 길이만 주어졌길래 뭔가 규칙이 있을 줄 알고 파고들었는데 .... ㅎㅎ;

string 길이가 최대 3'000이라 정확하게 계산해보진 않았지만 다 돌려도 시간이 오버될 것 같지는 않더라

그렇다고 너무 브루트포스면 안되고 최적화를 해줘야 풀린다. 그래서 그리디 태그가 붙은 듯.

 

문자열...너무싫다...

 

#include<bits/stdc++.h>
using namespace std;
#define X first 
#define Y second
#define rep(i,x,y) for(ll i=x;i<y;i++)
typedef long long ll;
typedef pair<int,int> pii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*------------------------------*/


int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    string str; cin>>str;
    int ans = 0;
    int idx = 0;
    while(++ans){
        string tmp = to_string(ans);
        rep(i,0,tmp.length()){
            if(str[idx]==tmp[i]) idx++;
            if(idx==str.length()){
                cout<<ans<<'\n';
                return 0;
            }
        }
    }
}