[프로그래머스] [Python] Level3_N으로 표현

https://programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - N으로 표현

동적계획법 Dynamic Programming 문제이다.

경우에 따라서 검사하는 range를 동적으로 설정해주기에 동적계획법이라고 한단다...

https://gurumee92.tistory.com/164

프로그래머스 문제 풀이 N으로 표현

해법 풀이는 이분보다 더 잘 정리할 수가 없어서 링크로 첨부!

1차 시도

def solution(N, number):
    if N == number:
        return 1
    
    s = [set() for x in range(8)]

    for i, x in enumerate(s, start=1): #8개의 set에 
        x.add(int(str(N) * i)) #각 횟수만큼의 N을 넣음(연속으로 이어붙인 수)

    for i in range(1, len(s)): #i를 1~7순회(모든 set을 순환)
        for j in range(i): #j를 0~(i-1)순회
            for op1 in s[j]: #s[j]순회 수 
                for op2 in s[i-j-1]: #s[i-j-1]순회 수
                    s[i].add(op1+op2)
                    s[i].add(op1-op2)
                    s[i].add(op1*op2)
                    if op2 != 0: s[i].add(op1//op2)
        if number in s[i]:
            answer = i+1
            break
    else:
        answer = -1
    return answer

 

왜 마지막 return 때 i가 아니라 i+1을 return하는 지 이해가 안되어서 break 직전에 print(s)를 찍어봄

[
  # s(0)
  {5}, 
  # s(1)
  {0, 1, 10, 55, 25},
  # s(2)
  {0, 2, 4, 5, 6, 555, -20, -4, -50, 15, 11, 50, 275, 20, -5, 60, 125, 30}, 
  # s(3)
  { 0, 1, 2, 3, 130, 5, -250, 7, -120, 9, 10, 11, 6, 4, 270, 15, 16, 12, 20, 150, 280, 
    25, 26, 24, -100, 30, 35, 550, 300, 45, 560, 50, 5555, 54, 55, 56, 65, -55, -54, 75, 
    80, 3025, -45, -9, 2775, -550, 1375, -30, 100, -25, -24, 250, -20, 110, 111, -15, -270, 
    625, -2, -10, 120, -6, -5, -4, -3, -1}, 
  # s(4)~s(7)
  {55555}, {555555}, {5555555}, {55555555}
]

## answer = 4

 

i와 j는 경우의 수 계산을 위한 인덱싱이라 for문을 돌 때는 set 안에 숫자들에 접근해서 계산을 수행한다.

 

s라는 list안에 set에 접근하기 위해서는 list의 인덱스로서 접근해야한다.

즉, set은 0부터 7까지의 인덱스이다.

따라서 0으로 시작하는 list의 인덱스를 사용횟수로 return하기 위해서는 1을 더해줘야한다.

 

잘보면 s[0] 즉, N을 한 번 사용했을 때는 체크가 되지 않는다. 

프로그래머스 정답 입력할 때도 강의에서 본 답이 통과가 안돼서 찾아봤는데 N을 한번 사용한 경우의 테스트 케이스가 나중에 추가되었었다.

 

i를 1부터 순회해서 걸러지않은건가 싶어서 0부터도 순회해봤는데 같은 결과가 나왔다.

 

코드를 보면 j를 range(i)내에서 순회하는데 i가 0이면 저 range자체가 0이 되어서 안에 계산문을 수행하지 않는다.

물론 이것이 s를 도출하는 데에는 문제가 되지 않지만,

(어짜피 한 번 쓰는거니까 처음 set에 enumerate돌릴 때 들어감)

number가 포함인지 아닌지 걸러내는 if문이 그 이하의 for문에 있어서 answer가 1인 경우는 잡아내지 못한다.

 

그래서 아래 코드를 맨앞에 추가해서 해당 테스트케이스를 걸러냈다.

if N == number:
        return 1

 

💡최종로직

0. return의 최솟값이 8보다 크면 -1이니, 최댓값은 8.

  N을 최대 8번 사용할 수 있다

  N을 x번 써서 나타낼 수 있는 수들을 담을 set들의 list를 생성한다

0. 각 set에 연속으로 이어붙인 수를 먼저 다 넣어준다

1. i에 대해서 1~8 순회(모든 set을 한 번씩 돌면서)

  1-1. j에 대해서 0~i 순회

     1-1-1. [ j번 사용하는 경우 나온 수 ]와 [ i-j-1번 사용하는 경우 나온 수 ]에 대해 사칙연산을 수행한다

  1-2. 만약 i번째 set에 number가 있다면, i+1을 답으로 return 후 break

2. for문을 다 돌았는데도 없으면 만들 수 없는 것이니, -1을 return

 

이 문제 하나를 이해하는데 3일이 걸렸다ㅠㅜㅠㅜㅠㅜㅠㅜㅠ(정말로 울고싶...)

동적계획법이라는게 원래 어려운건가...

인덱스를 자유자재로 활용해야해서 쉽지 않았다.