[BOJ] 1515 수 이어 쓰기

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

1515번: 수 이어 쓰기

왜 난이도가 실버 4인지 모르겠다. 최소 실버 1은 되야하는 문제. 고민하다가 친구의 도움을 받아서 해결했다.

나는 처음에 조건을 걸어 풀려고 했다. 하지만 조건이 너무 많더라. 항상 느끼는 건데 이런 유형의 문제는 규칙이 너무 많다. 아니 어쩌면 규칙이 없을 수도 있다. 이런 문제를 만난다면 규칙을 찾기 보다는 큰 데이터 하나를 만들어서 돌리는 것이 훨씬 빨리 문제를 풀 수 있다. 대신 시간복잡도를 만족하는지 확인을 반드시 해야 한다.

#include <iostream>
#include <string>
using namespace std;

//memo[i]에는 i번째 숫자는 어떤 수에 포함 되는지 저장된다.
//ex) 456457.... 첫번째 4가 1000번째라고 가정하면 memo[1000],[1001],[1002]에는 456이 들어간다
int memo[10000000];

int main(){
    string s,all_s="";
    cin>>s;
    int idx=0;
    for(int i=1;i<100000;i++){
        all_s+=to_string(i);
        for(int j=idx;j<idx+to_string(i).size();j++) memo[j]=i;
        idx+=to_string(i).size();
    }
    idx=0;
    for(int i=0;i<all_s.size();i++){
        if(all_s[i]==s[idx]) idx++;
        if(idx==s.size()){
            cout<<memo[i];
            break;
        }
    }
    return 0;
}