사용 언어: python 3.9.1
❓ Problem
📕 피드백
1. 발전 방향
최대한 모든 케이스 커버하려고 노력하기. 설계부터 노력하기!
너무 어렵게 푼 것 같다. 조금 더 쉽게 풀려고 노력해야겠다. 그리고 어차피 메인함수에서 재귀함수와 동일한 알고리즘을 쓸 거면 그냥 재귀함수로 통일해버리는 게 나을 것 같다.
2. 느낀점
일단 반성해야 할 게, 5시간 이상 풀었는데 노답이라서 결국 구글링으로 다른 사람 코드에서 정답 추출해서 내 코드랑 비교해가면서 어떤 케이스에서 틀리면 그 부분 고치는 식으로 풀었는데 이렇게 풀면 진짜 내가 반례 찾는 실력은 안 늘 것 같긴 하다. 편하긴 했다. 감사합니다.
for i in range(0, 1100):
print(i, end=" ")
m2 = main2(i); m1 = main(i)
# main2가 구글링해서 찾은 다른 사람 코드
print(m2, m1)
res = m2 == m1
if not res:
print("ERRORRR")
ans.clear()코테에서 가장 중요한 부분은 설계와 검증인 것 같다.
이 두가지 요소 다 알고리즘 문제를 푸는 게 익숙해지면 습관대로 잘 풀겠지만(마치 고딩 때의 수학적 습관처럼) 아직 나는 미숙해서 일단 차근차근 하는 게 먼저인 것 같다. 나만의 문제를 푸는 메커니즘을 구축하고 그걸 적용해나가면서 모든 유형의 문제들을 포괄할 수 있도록 조금씩 변형해 나가자. 조급해 하지 말자. 괜찮다.
🚩 Solution
1. 접근법
TRY 1
S(n,k)는 10^(n-1)의 자릿수를 가지고 k = 10^(n-1)번째 자리의 숫자를 만족하는 감소하는 수의 개수라고 하자. 즉 S(1,1)의 경우 {1}, S{2,2}={20, 21}이 있을 것이다.
S(n,1) = 1
S(n,2) = 1 + S(n-1, 1)
...
S(n,k) = 1 + S(n-1, 1) + S(n-1,2) + ... + S(n-1, k-1)
위 식과 같이 일반화시킬 수 있다는 개념에서 출발했다.
그런데 반례로, 100이나 200을 감소수로 포함하면 안된다는 것을 알게 되었다.
TRY 2
그래서 S(n,k) = S(n-1, 1) + S(n-1,2) + ... + S(n-1, k-1) 로, 1을 더해주는 것을 제거했다(getDescCnts 부분). 그리고 N = 1021인 경우 등등의 반례를 찾아 findDescNumber의 설정 오류를 고쳐 줬다.
2. 코드
import sys
from collections import deque
# sys.setrecursionlimit(10 ** 9)
memo = []; N = 0; cnt = 9
ans = deque()
def main():
global memo, N, cnt
N = int(sys.stdin.readline())
if N <= 9:
print(N); return
elif N >= 1023:
print(-1); return
memo += [0]*10, [1]*10, [0]*10,
digit = 2; front = 1; cnt =9
last = (0, 0, 0) # dummy init
while(cnt < N):
last = (digit, front, cnt)
memo[digit][front] = getDescCnts(digit, front)
cnt += memo[digit][front]
if front == 9:
memo += [0]*10,
# memo[아무][0] = 1: 나중에 가지 칠 때 000인 부분도 있을 것이므로
digit += 1; front = 1
else:
front += 1
if cnt == N:
last_digit, last_front, _ = last
while(last_digit>0):
ans.append(last_front)
last_front -= 1; last_digit -= 1
else:
last_digit, last_front, cnt = last
findDescNum(last_digit, last_front)
print(int(''.join(map(str, ans))))
def findDescNum(digit, front):
global cnt
if cnt == N:
# 4321,... 같은 애들 소외되지 않게 추가해주기
while(digit>0):
ans.append(front)
digit -= 1; front-=1
else:
temp = cnt
for k in range(front):
pre_temp = temp
temp += memo[digit-1][k]
if temp >= N:
cnt = temp if temp==N else pre_temp
findDescNum(digit-1, k)
ans.appendleft(front)
break
def getDescCnts(digit,front):
# S(digit, k) = S(digit,1) + ... + S(digit, k-1)
if digit == 1:
return 1
cnt = 0
for k in range(front):
cnt += memo[digit-1][k]
return cnt
main()설명
main: cnt가 N보다 커질 때까지 memo에getDescCnts를 통해서 memo[digit][front]를 저장해 준다. cnt가 N보다 크거나 같아지면 while문에서 나온다. 이때,- cnt==N인 경우: 10^(digit-1) 자릿수가 front인, 즉 S(digit, front)인 케이스 중 가장 큰 감소하는 수의 경우(S(3,3)일 때 321) while문에서 나오자마자 cnt==N에 걸리므로 해당 수를 ans에 넣어준다.
- cnt ≠ N인 경우: memo[digit][front]에서 (digit, front)가 한 단계 더 올라가면 cnt>N인 경우임.
findDescNum에서 digit-1을 해주고 S(digit-1,1)부터 S(digit-1, front-1)까지의 cnt를 계속 더하며 확인해 cnt가 N보다 커지는 경우, main에서 했던 것과 동일한 알고리즘으로 재귀함수를 돌려 계속 하위 digit과 front에서 cnt==N이 되는 경우를 찾는다.- 재귀함수를 지속하다가 cnt == N이 되는 순간, digit와 front에 따라 ans에 append를 해줘 답을 찾는다.
getDescCnts: S(n,k) = S(n-1, 1) + S(n-1,2) + ... + S(n-1, k-1) 를 구해주는 함수. reduce를 써도 좋을 것 같다.
3. 결과
시간 복잡도 분석
digit, front 구하기 ⇒ O(digit*10)
재귀 함수 돌기 ⇒ O(digit*front)
이때 digit ≤ 10, 상수 시간에 했다고 봐도 되지 않을까?
