BAEKJOON Online Judge(BOJ) 문제입니다.
Baekjoon Online Judge
Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.
www.acmicpc.net
문제
https://www.acmicpc.net/problem/1038
1038번: 감소하는 수
음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를
www.acmicpc.net
내가 작성한 코드
import sys
read = sys.stdin.readline
def get_count(N, r, cnt, target):
for i in range(r):
if N == 1:
cnt += 1
if target == cnt:
return str(i), cnt
else:
k, cnt = get_count(N-1, i, cnt, target)
if target == cnt:
return str(i)+k, cnt
return "", cnt
def get_decrease(N):
if N < 10:
return N
cnt = 9
n = "0"
s = ""
while cnt != N and len(n) < 10:
for i in range(1, 10):
s, cnt = get_count(len(n), i, cnt, N)
s = str(i) + s
if cnt == N:
break
if cnt == N:
break
n += "0"
if len(n) == 10:
return -1
return s
N = int(read().rstrip())
print(get_decrease(N))
- 재귀
- 10, 20, 30, ..., 90, 100, 200, 300, ...에 대해 재귀
- 앞자리 수보다 작은 수마다 재귀
- 마지막 자리수에서 cnt 증가
- target == cnt면 탐색 중지
다른 사람이 작성한 코드
import sys
from itertools import combinations
n = int(sys.stdin.readline())
nums = list() # 모든 감소하는 수
for i in range(1, 11): # 1~10개의 조합 만들기 (0~9개니깐)
for comb in combinations(range(0, 10), i): # 0~9로 하나씩 조합 만들기
comb = list(comb)
comb.sort(reverse=True) # 해당 조합을 감소하는 수로 변경
nums.append(int("".join(map(str, comb))))
nums.sort() # 오름차순
try:
print(nums[n])
except: # 인덱스가 넘어가는 경우 -1 출력. 마지막 수 9876543210
print(-1)
- 조합
- 감소하는 수의 최대값은 9876543210
- 첫 번째 for문은 1의 자리수 ~ 10의 자리수 - 감소하는 수는 각 자리수가 동일한 값을 가질 수 없음
- 0~9의 수에서 r개 뽑은 조합의 내림차순은 무조건 감소하는 수 - combinations는 인덱스가 작은 값부터 선택
- combinations로 도출되는 결과는 오름차순
- 감소하는 수의 최대값은 9876543210
- 문제를 명확하게 이해하셨기 때문에 깔끔한 알고리즘과 코드가 나왔다고 생각함
[Python] 백준 1038 감소하는 수
1. 문제 링크 https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은
ryu-e.tistory.com
기억해야할 것
- 코드가 조잡함
- 코드 설계를 제대로 못했을 때 코드가 항상 조잡하게 짜여지는 듯
- 통과는 했지만, 사용되는 변수 / if-else 조건 등이 난잡함
- 특히 숫자에 대한 재귀 문제에서 많이 어려움을 느끼는듯
'코딩테스트' 카테고리의 다른 글
[백준][투포인터] 냅색문제 (0) | 2022.04.08 |
---|---|
[백준][그리디] 보석 도둑 (0) | 2022.04.01 |
[백준][재귀] Choose Your Own Arithmetic (0) | 2022.04.01 |
[백준][슬라이딩윈도우] 달려라 홍준 (0) | 2022.03.29 |
[백준][재귀] 종이의 개수 (0) | 2022.03.24 |