[TIL] 2021.09.17

오늘 한 일

• 프로그래머스 N으로 표현
• 코테

 

간단정리

Dynamic Programming 문제풀이

프로그래머스 N으로 표현

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

1. 주어진 숫자 N 을 이용하여 number 를 만들어야하며

2. N 을 사용한 횟수가 가장 적은 값을 리턴한다.

3. 최솟값이 8보다 크면 -1 을 리턴한다

 

처음에 접근이 힘들어서 문제를 20번은 읽어본 듯 하다.

 

N 을 4번 사용한 경우
-> N 1개 (+, -, *, /) N 3개
-> N 2개 (+, -, *, /) N 2개
-> N 3개 (+, -, *, /) N 1개
-> N 4개 (NNNN)

 

이 주석 부분이 핵심이다.

 

결국 N 이 4번 나와야되니 괄호건 N 을 붙인 숫자건 모든 경우의 수가 나올 수 있다.

N(1) 연산자 N(3)

N(2) 연산자 N(2)

N(3) 연산자 N(1)

N(4)

 

결국 Dynamic Programming 의 핵심인 점화식이 완성되고 문제를 해결할 수 있었다.

 

def solution(N, number):
    # N 을 1번 사용한 경우
    # N 을 2번 사용한 경우
    # .....
    # N 을 8번 사용한 경우
    # N 을 9번 이상 사용한 경우 (-1)

    # N 을 4번 사용한 경우
    # -> N 1개 (+, -, *, /) N 3개
    # -> N 2개 (+, -, *, /) N 2개
    # -> N 3개 (+, -, *, /) N 1개
    # -> N 4개 (NNNN)
    # ====================== End of Description

    # 8번 동작까지 답이 없으면 answer 는 -1 이다
    answer = -1
    # rs 에는 N 을 사용한 횟수 별 결과를 저장한다.
    # rs[0] = N 이 1번 // rs[1] = N 이 2번 ...
    rs = []
    # i = 1, 2, 3 ... 7, 8
    for i in range(1, 9):
        cases = set()
        cases.add(int(str(N) * i))
        # j = 8, 7, 6 ... 2, 1
        for j in range(0, i-1):
            # rs[0], rs[1], rs[2] ...
            for k in rs[j]:
                # rs[7], rs[6], rs[5] ...
                for l in rs[-j-1]:
                    cases.add(k + l)
                    cases.add(k - l)
                    cases.add(k * l)
                    if l != 0:
                        cases.add(k / l)
        # N 이 i 인 cases 중 정답 number 가 있을 시 사용횟수의 최솟값이다
        if number in cases:
            return i
        rs.append(cases)

    return answer

 

코테

 

모르는 문제들이 나왔다.

알고리즘 (구현?) 3문제, SQL 1문제

 

SQL 1문제는 mysql 문법을 찾아보며 해결할 수 있었다.

알고리즘은 풀어보지 못한 유형이 나와서 주석만 잔뜩적고 풀이하다가 시간을 다 보냈다.

공부한셈 치기로 하고 문제를 복기하여 풀어보고 정리해보았다.

• 3문제 중 1번문제 복기 및 풀이완료.
• 2번은 기억나는대로 문항을 복구해뒀고 추후 풀어볼 예정.
• 3번은 풀어보지도 못했다.

코테 특성상 문제 공개나 풀이 공개는 불가하며 유사한 문제를 가져와봤다.

아래 문제를 응용한 문제같았다.

결국 경험이 모자라서 코테기회로 공부를 할 수 있었다.

 

https://nypc.github.io/2018/2018_online_14.html

https://nypc.github.io/2018/2018_online_14.html

 

느낀점

• DP 를 열심히 봤는데 DP 문제가 안나와서 아쉬운 코테였다.
• 경험이 부족함을 크게 느꼈고 결국 답은 많은 문제를 풀어보는 것임을 몸으로 느꼈다.
• 추석 연휴에는 PC 가 없는 본가에 있을 듯.. (있는데 고장났다고 한다) TIL 휴식예정?!