백준 17255 - N으로 만들기 (파이썬)
글 작성자: pental
https://www.acmicpc.net/problem/17255
풀이
문제의 핵심은 주어진 숫자 N을 만들 수 있는 가능한 순서열을 모두 찾아 그 개수를 세는 것이다.
여기서는 재귀적 브루트포스 기법을 활용하여 주어진 숫자 N을 만들 수 있는 모든 경우를 탐색하는 방식을 사용한다.
재귀 함수를 구현하였고, 해당 재귀함수의 기능은 다음과 같다.
- n이 현재까지 만들어진 숫자 문자열
- N을 만들수 있는 모든 방법을 재귀적으로 탐색한다.
- n == N 을 통해서 현재 n이 N과 같다면 하나의 유효한 방법을 찾은 것이므로 1을 반환한다.
- N.find(n) == -1 을 통해서 n이 N에 포함되지 않는 부분 문자열이면 더 탐색할 필요가 없기에 0을 반환한다.
- n의 앞 또는 뒤에 숫자 i(0~9)를 추가한 left와 right을 만든다.
- 예를 들어 n="2"인 경우
- left = "02" (왼쪽 추가)
- right = "20" (오른쪽 추가)
- left == right인 경우 중복 호출을 방지하여 한 번만 재귀 호출.
- 그렇지 않다면 좌우 각각 재귀적으로 호출.
- 예를 들어 n="2"인 경우
코드
# 백준 17255 - N으로 만들기
# 분류 : 브루트포스
N = input()
def f(n) :
if n == N :
return 1
if N.find(n) == -1 :
return 0
ret = 0
for i in range(10) :
left = str(i) + n
right = n + str(i)
if left == right :
ret += f(left)
else :
ret += f(left)
ret += f(right)
return ret
answer = 0
for i in range(10) :
answer += f(str(i))
print(answer)
'Programming > 백준' 카테고리의 다른 글
백준 2075 - N번째 큰 수 (파이썬) (0) | 2025.03.11 |
---|---|
백준 16439 - 치킨치킨치킨 (0) | 2025.03.11 |
백준 13164 - 행복 유치원 (파이썬) (0) | 2025.03.10 |
백준 17951 - 흩날리는 시험지 속에서 내 평점이 느껴진거야 (파이썬) (0) | 2025.03.09 |
백준 2503 - 숫자 야구 (파이썬) (1) | 2025.03.09 |
댓글
이 글 공유하기
다른 글
-
백준 2075 - N번째 큰 수 (파이썬)
백준 2075 - N번째 큰 수 (파이썬)
2025.03.11 -
백준 16439 - 치킨치킨치킨
백준 16439 - 치킨치킨치킨
2025.03.11 -
백준 13164 - 행복 유치원 (파이썬)
백준 13164 - 행복 유치원 (파이썬)
2025.03.10 -
백준 17951 - 흩날리는 시험지 속에서 내 평점이 느껴진거야 (파이썬)
백준 17951 - 흩날리는 시험지 속에서 내 평점이 느껴진거야 (파이썬)
2025.03.09