1이상 4이하의 숫자로만 이루어져 있으면서, 정확히 해당 숫자만큼 연달아 같은 숫자가 나오는 숫자를 아름다운 수 라고 부릅니다.
예를 들어 1333221는 1이 1번, 3이 3번, 2가 2번 그리고 1이 1번 연속하여 나오므로 아름다운 수 입니다.
이때 동일한 숫자에 대해 연달아 같은 숫자의 묶음이 나오는 것 또한 아름다운 수 입니다. 예를 들어 111, 22222222와 같은 수 역시 1이 1번 나온 것이 3번 반복되었고, 2가 2번 나온 것이 4번 반복되었다고 할 수 있기 때문에 아름다운 수라고 할 수 있습니다. 다만, 222의 경우에는 2가 2번 나온 뒤, 다시 2가 1번 나왔으므로 아름다운 수가 아닙니다.
n자리 아름다운 수가 몇 개 있는지를 구하는 프로그램을 작성해보세요.
입력 형식
첫 번째 줄에는 n이 주어집니다.
1 ≤ n ≤ 10
출력 형식
n자리 아름다운 수의 개수를 출력합니다.
입출력 예제
예제1
입력:
3
출력:
4
못풀었다....
핵심은 아름다운 수인지 판별하는 함수 만들기
아름다운 수 조건을 확인하는 함수를 만들어야 한다.
<아름다운 수 조건> 은 다음과 같다.
1이 나오면 1개든 2개든 3개든 상관 없다.
현재(0) 수가 2이 나오면 다음 수(1)가 이전 수(0)가 2와 같은지 확인하고 그 다음 수(2)를 확인한다.
현재(0) 수가 3이 나오면 다음 수(1)와 그 다음 수(2)가 3과 같은지 확인하고 그 다음 수(3)를 확인한다.
이때 확인하다가 다음 수로 넘어갈때 n자리 수를 넘어가면 안된다.
위를 구현해야 한다.
def is_beautiful(n):
idx = 0
# 연달아 같은 숫자가 나오는 시작 위치를 잡는다.
while idx < n:
# 만약 연속하여 해당 숫자만큼 나올 수 없다면
# 즉 현재 위치(idx)에서 seq[idx]개 만큼 점프할건데 그걸 n자리수를 넘어가면
# 아름다운 수 조건에 위배됨
if idx + seq[idx] - 1 >= n:
return False
# 연속하여 해당 숫자만큼 같은 숫자가 있는지 확인
for j in range(idx, idx + seq[idx]):
if seq[j] != seq[idx]: # 연속하는가?
return False
idx += seq[idx] # idx는 idx번째 수 만큼 점프함
# 예) idx가 0이고 seq[0]가 2면 2칸씩 연속한지 확인할 것임
return True
이 함수 코드를 보면 idx=0번째 수부터 본다.
예를 들어 112211133인 수를 seq=[1,1,2,2,1,1,1,3,3]에 넣어 확인한다고 하자
idx=0번째 수는 seq[idx]가 1이다.
if idx + seq[idx] -1 -> 현재 위치에서 현재 위치의 수만큼 이동해도 n자리수를 안넘는다.
0부터 1까지 즉 자기자신만 보면 되므로 2번째 조건의 for문도 넘어간다.
idx += seq[idx]로 idx=1번째를 확인한다.
역시 1이므로 자기자신만 확인하고 다음 번째 idx=2로 넘어간다.
현재 idx는 2이고 seq[2]는 2이다. 2 + seq[2] - 1은 3으로 n자리를 넘어가지 않고
2부터 3까지 확인할 것이므로 range(idx, idx+seq[idx])번째 수들이 연속한지 확인한다.
7,8,9번째 수를 확인해서 세 숫자가 연속하는지 봐야하지만 n자리수가 넘어가서 확인이 불가하다.
즉 3은 연속해서 3이 안나오는 아름다운 수가 아니다
전체 코드
import sys
def is_beautiful(n):
idx = 0
# 연달아 같은 숫자가 나오는 시작 위치를 잡는다.
while idx < n:
# 만약 연속하여 해당 숫자만큼 나올 수 없다면
# 즉 현재 위치(idx)에서 seq[idx]개 만큼 점프할건데 그걸 n자리수를 넘어가면
# 아름다운 수 조건에 위배됨
if idx + seq[idx] - 1 >= n:
return False
# 연속하여 해당 숫자만큼 같은 숫자가 있는지 확인
for j in range(idx, idx + seq[idx]):
if seq[j] != seq[idx]: # 연속하는가?
return False
idx += seq[idx] # idx는 idx번째 수 만큼 점프함
# 예) idx가 0이고 seq[0]가 2면 2칸씩 연속한지 확인할 것임
return True
def DFS(cnt):
global ans
if cnt == n:
if is_beautiful(n): # n자리 수가 정해지면 그게 아름다운 수인지 확인
ans += 1
return
# 1이상 4이하의 숫자로만 이루어져 있으면서,
for i in range(1, 5): # 예) 111에서 444까지
seq.append(i)
DFS(cnt + 1)
seq.pop()
if __name__=="__main__":
n = int(input()) # n자리
ans = 0
seq = []
DFS(0)
print(ans)
