[코드트리_IL]_백트래킹_아름다운수

 

https://www.codetree.ai/

나무랄 데 없는 코드트리 식목일 이벤트

해당 문제는 코드 트리에서 가져왔습니다.

##문제 풀이전 코드 트리에 대하여##

3월 말부터 약 6주에 걸쳐 진행되는 코드 트리 camp에 참여하게 되었습니다. 평소 어려워했던 유형만 모아져 있는 시뮬레이션, 완전 탐색, dfs/bfs, dp 쪽을 조금 더 도움을 받아 깊게 공부하고 싶어 IL과정을 수강하게 되었습니다. 1주 차엔 dx, dy 테크닉 , 2주 차엔 시뮬레이션이 진행되었고 3주 차인 지금은 백트래킹을 학습 중에 있습니다.

코드 트리는 기본, 쉬움, 보통, 어려움, 실력체크로 총 5단계로  난이도가 나눠져 있으며 하나의 기본 개념을 배우고 차근히 난도가 높은 문제를 푸는 계단식 형태의 커리큘럼이 구성되어 있습니다. 문제, 해설(꼼꼼하게 되어있음), 질문(빠른 답변)등 코딩 공부를 함에 있어서 너무나 좋은 사이트입니다. 취업용 코딩 테스트 공부를 막 시작하시는 분들이나 몇몇 알고리즘에 어려움을 느끼는 골드라인분들께 강력추천드리는 사이트입니다.!!

문제

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자리 아름다운 수의 개수를 출력합니다.

문제 해결

백트래킹으로 중복 조합 가능한 n자릿수를 뽑아 배열에 넣어준 후

그 값들이 아름다운 수인지 확인하는 방법으로 코드를 구성했습니다.

 

import sys
sys.setrecursionlimit(10**6)
n = int(input())
numbers = []
num = [i for i in range(1, 5)]
cnt = 0
def f(box): #백트래킹으로 numbers배열에 조합가능한 n자리수를 담아준다
    global cnt
    if len(box) == n:
        numbers.append(box)
        return
    for i in num:
        f(box + [i])

#1~4사이의 숫자로만 이루어져 있기때문에 숫자별로 아름다운수를 확인하고 초기화해준다
def check(x):
    global cnt
    for i in range(n):
        if x[i] == 1:
            continue
        elif x[i] == 2 and 0<=i and i+1<n:
            if x[i:i+2] == [2]*2:
                x[i:i+2] = [1]*2
            else:return
        elif x[i] == 3 and 0<=i and i+2<n:
            if x[i:i+3] == [3]*3:
                x[i:i+3] = [1]*3
            else:return
        elif x[i] == 4 and 0<=i and i+3<n:
            if x[i:i+4] == [4]*4:
                x[i:i+4] = [1]*4
            else:return
        else:
            return
    cnt += 1
f([])
for i in numbers:   #모든 숫자에 대해서 check하여 cnt값에 변화를 준다.
    check(i)
print(cnt)