[코드트리 챌린지] 7주차 (10/17-10/23), 백트래킹

두둥

7주차..

654 -> 610 😶‍🌫️

다시 점수 복귀..

실력진단평가 풀면서 백트래킹 문제에서 막혔는데, 어어...여기서 막히면 안되는데...? 생각이 들었다.

공부했지만 문제에 따라 풀수도~ 못풀수도~ 있는거니까 점수에 연연하면 안되는데, 알면서도 쭉쭉 상승세로 가다가 막상 하락세로 가니까 마음이 쫌 아팠다...

힘들게 올린 점수였는데,,

하지만, 이 기회에 백트래킹 재정비하면서 다시 한번 풀어봤다.

백트래킹 카테고리 문제를 풀면서 어려워서 해설을 본 문제들도 많아서 이번 기회에 다시 풀게 되어서 오히려 다행이었다!

오히려 좋아

그래서 이번주는 개념을 복습한다기 보단, 풀었던 문제들을 다시 풀어보는 그런 주차가 되었다

 

해결한 문제

# 아름다운 수

이 문제는 처음 백트래킹 학습했을 때, 풀이를 보고도 계속 이해를 못해서 보고 또보고 보고 또 봤었던 문제다.

그러고 나서 지금 2주만에 다시 풀면서 풀이를 전혀 보지 않고 내가 생각해낸 로직대로 풀어보았다.

문제는 아래와 같다.

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자리 아름다운 수가 몇 개 있는지를 구하는 프로그램을 작성해보세요.

 

나의 풀이 전략
1. 기본 백트래킹 재귀(1부터 4까지)

2. + 조건(지금까지 배열에 넣어져있는 수 + 넣을 수 <= 자릿수 n)

 

나의 풀이

n = int(input())
arr=[]
cnt = 0

def beautiful(curr_num):
    global cnt
    if curr_num == n:
        cnt += 1

    for i in range(1, 5):
        if len(arr)+i<=n:
            for _ in range(i):
                arr.append(i)
            beautiful(curr_num + i)
            for _ in range(i):
                arr.pop()

beautiful(0)
print(cnt)

 

토론으로 해결하다👀

이 문제를 풀면서 로직은 맞는거 같은데 답이 계속 안나와서 엄청 고민을 했던 부분이 있었다.

계속 혼자서 머리를 싸매고 하다가 왜 안되는지 알아야겠어서 코드트리의 토론 기능을 사용해서 빠르게 그 답을 얻을 수 있었다.

질문

답변

이렇게 질문을 남기고, 사진과 같은 답변을 받을 수 있었다.

답변을 보니 바로 내가 저지른 실수가 무엇인지 단번에 알 수 있었다.

i번을 돌려서 배열에 넣어줬으면서 curr_num + 1을 해주고 있었던 것이다. curr_num + i로 바꿨더니 바로 해결되었다.

 

토론 탭은 처음 사용해봤는데, 답변도 빠르게 돼서 해설과는 다른 내 풀이의 문제점을 알 수 있다는 점에서 너무 명쾌했다!