[Programmers 코딩테스트] 동적계획 - N으로 표현

📌 알고리즘 정리

2021.04.28 - [알고리즘] - 동적 계획법(Dynamic Programming)

---

📃 문제

괄호, 이어붙이기(55, 555 같은), 사칙연산 모두 가능이기 때문에

경우의 수가 다양했고 멍청한 저는 일단 하나씩 써보면서 문제의 규칙을 찾아보기로 하였습니다...

---

✍ 풀이과정

동적계획법 개념 정리하고 나서 이 문제를 봤을 때,

N 사용 횟수에 따라서 저장하고 횟수가 많아질 때 그 전의 저장해둔 값들을 사용해야 겠다는 생각이 들었습니다.

 

괄호를 어떻게 해야할지 감이 안 잡혔는데 다 써보고나서 이해했습니다...(너덜너덜)

 

N 사용 횟수가 3인 경우,

- 3개 이어붙이기

- (2) + 1

- 1 + (2)

로 나누어질 수 있습니다.

이때, 2 +1에서 '+'로 나누어진 경우 "(2) + (1)"처럼 괄호가 붙는다고 생각하고 문제를 풀었습니다.(괄호에 따라 결과가 달라지기 때문에)

 

1 + 1 + 1도 있는데 왜 빼는지라는 생각이 드실 수도 있는데

(N) ◇ (N) ◇ (N) 은 들어갈 연산자에 따라서 결국 괄호가 묶이게 되는데

(◇은 중간에 들어갈 연산자를 뜻합니다!)

 

예를 들어서 (5) + (5) / (5)라 치면

5 + (5/5)로 다시 묶이게 되어서 "1 + 2"형태가 되는 것입니다.

중복이 일어나기 때문에 이는 굳이 따로 생각할 필요가 없습니다.

 

N 사용 횟수가 4인 경우에,

- 2 + 1 +1 / 1 + 2 +1 / 1 + 1 +2

- 1 + 1 + 1 +1

인 경우도 있는데

 

1 + 1 + 1 +1 인 경우는 위에서 설명한 것과 같이

2 + 1 +1 / 1 + 2 +1 / 1 + 1 +2 형태로 묶일 수 있고(5*5 +5 + 5)

이는 또 2+2, 3+1, 1+3 형태로 묶일 수 있으므로 중복되는 경우입니다.

 

이런 식으로 생각을 하고 코드를 짜기 시작했는데도 어렵더라구요~,~

 

Top-down, Bottom-up 중 어느 방식을 선택해야할지 먼저 생각해봤는데

작은 수부터 쌓아가는 것이 맞다는 생각이 들어서 Bottom-up 방식을 사용해야겠다고 생각했고

문제에서 최솟값이 8보다 크면 -1을 return한다고 하였으므로

횟수가 8일 때까지만 구해면 될 듯 합니다!

 

이어붙이는 경우는 아예 먼저 저장해두고 시작합니다.

중복을 피하기 위해서 set()에 저장해줍니다.

F=[set() for i in range(8)]

for n in range(8):
        F[n].add(int(str(N)*(n+1)))

 

처음에는 set이 아닌 list에 저장했다가 아주 난리난리였습니다....

 

 

이제 이어붙이지 않는 경우를 생각해봅시다!

 

F[0], 즉 N 사용 횟수가 1일 때는 이어붙인 값밖에 없기 때문에 뛰어넘고 F[1]부터 시작합니다.

사용 횟수와 index값이 "-1" 차이가 나기 때문에 for문 돌릴 때 약간 헷갈렸는데

 

n을 F의 index, N의 사용 횟수를 cnt라고 하면

n = cnt -1

F[n] = F[i] + F[n-i-1] (0<=i < n)

라고 정리할 수 있겠습니다.

 

점점 F[n] 채워가면 F[n]의 크기는 엄청나게 불어납니다.

number와 같을 때를 체크해줘야 하는데 가뜩이나 4중 for문인데

어디에서 체크해줘야 효율성이 좋을까 생각하다가

 

1 .4번째 for문에서 +, -, *, / 할때 바로 체크할지

2. F[n]을 모두 저장한 후에 체크할지

 

1번은 코드가 조금 지저분해질 것 같아서 그냥 2번으로 선-택

def solution(N, number):
    if N==number:
        return 1
    F=[set() for i in range(8)]
    for n in range(8):
        F[n].add(int(str(N)*(n+1)))

    for n in range(1,8):
        for i in range(n):
            for a in F[i]:
                for b in F[n-i-1]:
                    F[n].add(a+b)
                    F[n].add(a - b)
                    F[n].add(a * b)
                    if b!=0:
                        F[n].add(a // b)

        if number in F[n]:
            return (n+1)
    
    return -1

 

 

문제는 복잡하지만 코드는 깔끔하게 딱 짜이는 것 같네욥!

---

💯 정확성/효율성 테스트

---

🏆 고수님들의 코드

다른 분들의 풀이를 제대로 뜯어보지는 못했고 휘뚜루봤는데 저와 비슷했던 것 같습니다!

 

문제 푸는데 너무 힘빠져서 오늘은 뛰어넘겠숨네다......

---

🔔 새롭게 알게 된 내용

---

🤔 개선 방안

---

💌 질문/피드백

---

🏃‍♀️ 마치며...