[백준] 31263. 대한민국을 지키는 가장 긴 힘 (python)
https://www.acmicpc.net/problem/31263
문제
부대 병사들은 전역의 염원을 담은 전역일 페이퍼를 만들기로 결심했다. 전역일 페이퍼란, 긴 종이에 병사들의 남은 복무 일수를 띄어쓰기 없이 한 줄로 나열하는 것이다. 가령, 남은 복무 일수가 각각 124일, 631일, 2일 남은 병사들이 순서대로 전역일 페이퍼를 작성하면, 종이에는 1246312라는 수가 적히는 것이다. 공군의 최대 복무 일수는 641일이기 때문에, 전역일 페이퍼에 본인의 남은 전역일을 작성한 사람들은 모두 1이상 641이하의 수만을 작성하였으며, 수 앞에 불필요한 0을 붙이지 않았다고 한다.
각 병사가 가능한 남은 복무 일수인 1이상 641이하의 수만을 작성했다는 사실을 토대로 전역일 페이퍼를 작성한 병사 수의 최솟값을 구하기로 했다.
입력
첫 번째 줄에 전역일 페이퍼에 적힌 수의 자릿수 이 주어진다.
두 번째 줄에 전역일 페이퍼에 적힌 수를 나타내는 길이 의 정수 가 주어진다.
주어진 수 가 전역일 페이퍼에 적힌 수가 될 수 있음이 보장된다.
출력
첫 번째 줄에 전역일 페이퍼를 작성한 병사 수의 최솟값을 출력한다.
제한
- 1≤ N ≤ 5000
- 모든 입력은 정수이다.
처음에는 문자열로 입력받은 전역일을 나열한 숫자를 하나씩 반복문을 돌리면서
숫자를 만들어 1 <= number <= 641 조건을 만족하는지 확인하고, 만족하면 넘어가고, 만족하지 않으면 카운팅해서 다음 숫자로 넘어가는 방식으로 구현했었는데
이렇게 했을 때 대부분의 예제는 돌아갔지만
6
560010
위 예제를 받았을 때에는
560, 10 -> 이렇게 나눠져서 최적의 해가 나오지 않았다.
결국 이 문제는 '수 앞에 불필요한 0을 붙이지 않았다고 한다.' 라는 설명이 있기 때문에 0이 연속해서 나올 경우 예외가 발생할 수 있다는 점을 주의깊게 고려해야 했다.
그래서 560010 과 같이 0이 연속하는 경우 5 / 600 / 10 과 같이 숫자를 나눌 수 있도록 코드를 다시 짰다.
n = int(input())
s = input()
# 해당 숫자로 파악할 수 있는 병사의 최솟값을 저정하는 리스트
d = [0] * (n+1)
d[0] = 1
# 한 병사의 전역일을 계산하기 위한 변수
number = int(s[0])
# 이전 병사의 전역일을 계산하기 위한 변수
prev = number
for i in range(1, n):
number = number * 10 + int(s[i])
# 조건을 만족하는 경우 다음 병사로 넘어갈 필요 없음
if 1 <= number <= 641:
d[i] = d[i-1]
# 조건을 만족하지 않으면 다음 병사의 전역일 계산으로 넘어감
else:
# 만약 해당 숫자가 0이라면
if int(s[i]) == 0:
# 0이 아닐때까지 앞으로 거슬러 올라감
temp = 1
for j in range(i, 0, -1):
if int(s[j]) == 0:
temp = temp * 10
else:
temp = temp * int(s[j])
break
# 거슬러 올라가 계산된 숫자를 이전 병사의 전역일로 저장
prev = temp
# 해당 숫자가 0이 아니라면
else:
# 그냥 그 숫자를 이전 병사의 전역일로 저장
prev = int(s[i])
# 병사의 숫자를 카운팅 + 1
d[i] = d[i - 1] + 1
number = prev
print(d[n-1])
1. d리스트는 해당 숫자까지 파악할 수 있는 병사의 최솟값을 의미한다.
ex) 560010
-> d[0] : 5 일 경우 병사의 최솟값 -> 1
-> d[1] : 56 일 경우 병사의 최솟값 -> 1
-> d[2] : 560 일 경우 병사의 최솟값 -> 1
2. 입력받은 전역일나열한 문자열을 하나씩 반복문을 돌린다.
3. 그러다가 조건을 만족하지 않는 숫자가 나올 경우
ex) 5 -> 만족
56 -> 만족
560 -> 만족
5600 -> 불만족 (641보다 크므로)
4. 해당 위치의 수의 자리가 0인지를 확인한다.
- 0이라면 앞으로 거슬러 올라가 가능한 숫자를 만들어 prev에 저장한다.
prev = 600
- 0이라면 해당 수의 자리를 prev에 저장한다.
prev = 1
5. 병사의 숫자를 카운팅한다.
6. prev를 이용해 다음 병사의 전역일 계산을 시작한다.
0을 만났을 때 코드가 너무 복잡한 것 같아서 이게 통과가 될까 싶었는데, 일단 100점이 나오긴 해서 놀랐다.
다른 분들의 코드를 여러개 보니까 역시나 다들 0을 만났을 경우에 대해서 깊이 고민하신게 느껴졌다.
다른 코드들을 보다보니 이 문제가 전역일의 조건(1보다 크거나 같고 641보다 작거나 같다)이 있기 때문에
만들 수 있는 전역일의 자리수가 3개가 최대라는 점과 0이 문제가 된다고 해도, 0의 개수는 1개 혹은 2개라는 점을 이용해서 더 간단하게 풀 수도 있을 것 같아서 다른 풀이를 고민해봐야 겠다.