[백준 1515] 수 이어 쓰기

문제 링크 => 1515번: 수 이어 쓰기 (acmicpc.net)

1515번: 수 이어 쓰기

---

문자열을 이용한 구현 문제이다.

 

먼저 정해진 것은 아니지만 [1, 99999] 범위 내의 모든 숫자을 이어주도록 하는 문자열 s를 설정하였다.

 

그리고 123456789101112... 이런식으로 나아갈 때 [x, y] 범위 내의 숫자를 z 라고 설정하기 위해 1차원 배열 dp를 둬서 dp[x] = dp[x + 1] = ... = dp[y - 1] = dp[y] = z 이런 식으로 설정하였다.

 

입력한 문자열을 inS라 할 때, inS 의 index를 idx, 설정한 문자열 s의 index를 i 라 하고 i 를 1씩 증가시키면서 inS[idx] 와 비교하도록 한다.

 

비교할 때 inS[idx] == s[i] 인 경우 inS의 idx를 1 증가시키면서 동시에 문자열 s의 index도 1 증가시키고 같지 않은 경우는 문자열 s의 index를 계속해서 증가시킨다.

 

그렇게 해서 inS 의 모든 문자를 탐색한 경우 문자열 s와 inS가 마지막으로 같았던 index 를 가지고 dp[idx] 를 출력하면 답이 된다.

 

예를 들어서 234092 로 위 과정을 적용하면 다음과 같다.

 

1. 234092 (idx = 0) / 1234... (i = 0)    => inS[idx] 와 s[i] 가 같지 않으므로 i 만 증가

2. 234092 (idx = 0) / 2345... (i = 1)    => inS[idx] 와 s[i] 가 같으므로 idx, i 동시에 증가

3. 34092   (idx = 1) / 3456... (i = 2)    => 같으므로 idx, i 동시에 증가

4. 4092     (idx = 2) / 4567... (i = 3)    => 같으므로 idx, i 동시에 증가

5. 092       (idx = 3) / 5678... (i = 4)    => 같지 않으므로 i 만 증가

...

6. 092       (idx = 4) / 01112... (i = a)   => 같으므로 idx, i 동시 증가

...

7. 92         (idx = 5) / 92021... (i = b)   => 같으므로 idx, i 동시 증가

8. 2           (idx = 6) / 2021...   (i = c)   => 같으므로 idx, i 동시 증가

9. (idx = 7) / 0212... (i = d)    =>  inS 의 문자열을 모두 탐색하였으므로 dp[i - 1] 를 출력한다.

 

이때 dp[i - 1] 는 [x, y] 범위 내의 숫자 z 라고 할 때 [x, y] 범위 내의 숫자 i - 1 에 대하여 숫자 20 이므로 20 이 출력된다.

 

풀이 Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#define endl '\n'

using namespace std;

int dp[1000000];

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	string inS, s = "";
	cin >> inS;

	int idx = 0;
	for (int i = 1; i < 100000; i++) {
		s += to_string(i);
		for (int j = idx; j < idx + to_string(i).size(); j++) {
			dp[j] = i;
		}
		idx += to_string(i).size();
	}

	idx = 0;
	for (int i = 0; i < s.size(); i++) {
		if (idx == inS.size()) {
			cout << dp[i - 1];
			break;
		}
		if (inS[idx] == s[i]) idx++;
	}
	
	return 0;
}