Awesome

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

dp[0] = N을 0번 사용해서 만들 수 있는 숫자들의 그룹

dp[1] = N을 1번 사용해서 만들 수 있는 숫자들의 그룹

dp[2] = N을 2번 사용해서 만들 수 있는 숫자들의 그룹

dp[3] = N을 3번 사용해서 만들 수 있는 숫자들의 그룹

        = [NNN] + dp[1]에 있는 모든 숫자들과 dp[2]에 있는 모든 숫자들을 +, -, *, / 해서 만들 수 있는 숫자들의 그룹

점화식:

dp(n) = [dp(i)의 모든 숫자들 + - * ÷ dp(n-i)의 모든 숫자들] (i = 1부터 n-1)

(점화식에서 55 555 5555 등의 숫자는 제외했다. 이러한 숫자들은 n마다 하나씩 있다. N을 n번 써준 숫자.)

문제에서 괄호까지 넣을 수 있다고 해서 헷갈렸다.

예를 들어 5를 3개 가지고 만들 수 있는 연산식 중 5 + 5 ÷ 5 가 있을 때,

(5 + 5) ÷ 5 와 5 + (5 ÷ 5)는 다른데 이걸 어떻게 고려해줘야 하나? 싶을 수도 있을 것이다.

하지만 다시 생각해보면 (5 + 5)와 (5 ÷ 5)는 5를 2개 가지고 만든 연산식이다. 

즉 저 식들을 일반화해서 생각해보면

[5를 2개 가지고 만들 수 있는 수] + - * ÷ [5를 1개 가지고 만들 수 있는 수]

[5를 1개 가지고 만들 수 있는 수] + - * ÷ [5를 2개 가지고 만들 수 있는 수]

가 되는 것이다. 그냥 두 번 쓴 게 아니다. -, ÷일 때는 식의 순서가 달라지면 결과도 달라질 수 있다.

j의 range를 (1, i // 2 + 1)로 잡은 이유는 

우선 dp[0]은 0이므로 볼 필요가 없다. dp[n] = dp[0] + - * ÷ dp[n]도 맞긴 한데, 어차피 다 중복되는 숫자들이라 해줄 필요가 없다.

range의 두번째 인자가 i // 2 + 1 라는 것은 j를 i // 2 까지 보겠다는 건데, 그 이유는 어차피 중복되기 때문이다.

예를 들어 dp(4) = dp(1) + - * ÷ dp(3), dp(2) + - * ÷ dp(2), dp(3) + - * ÷ dp(1) 인데 기울임 처리한 마지막 연산은 밑줄 친 첫번째 연산과 앞 뒤를 바꿔준 것 밖에는 다르지 않다. +와 *는 앞뒤가 바뀌어도 결과가 같기 때문에 신경 안 써도 되고, -와 ÷만 앞뒤로 바꿔서 해주면 된다.

i, j, k, m 등 요상한 변수가 많아서 헷갈릴 수 있는데 변수에 별다른 뜻이 없어서 어쩔 수가 없었다...

i = 2 부터 해서 직접 변수 안에 무엇이 들어가나 써보면 좀 이해하기 쉬울 것이다.

# Lvl3. N으로 표현


def solution(N, number):
    answer = 0
    dp = [0, {N}]  # N을 0번, 1번 가지고 만들 수 있는 수들의 집합
    
    if N == number:
    	return 1
        
    for i in range(2, 9):  # N을 2번 ~ 8번을 가지고 만들 수 있는 수들의 집합 구하기
        case = {int(str(N)*i)}  # N, NN, NNN ...
        for j in range(1, i // 2 + 1):  # dp(3) = [dp(1) +-*/ dp(2)] 여기서 j=1, i-j=2
            for k in dp[j]:
                for m in dp[i-j]:
                    case.add(k + m)
                    case.add(k * m)
                    
                    # j는 i의 절반까지만 구하고 연산할 때 앞뒤를 바꿔줌
                    case.add(k - m)
                    case.add(m - k)
                    if k > 0:
                        case.add(m // k)
                    if m > 0:
                        case.add(k // m)

        if number in case:
            #print(dp)
            return i
        else:
            dp.append(case)

    return -1

http://boj.kr/14501 

페이의 최댓값을 구하려면 각각의 모든 날짜에 대해서 선택을 하거나 / 하지 않거나 모든 경우를 고려해 봐야 한다.

점화식

d[n] = max(d[n+1], d[n+T[n]] + P[n])

=

N~n일까지의 최대 페이 = max(N~n+1일까지의 최대 페이, N~n+T[n]까지의 최대 페이+n일의 페이)

=

N~n일까지의 최대 페이 = max(n일에 일을 하지 않았을 때, n일에 일을 했을 때)

즉 d[i]가 0일부터 i일까지의 페이가 아니라 i일부터 N일까지의 페이라고 생각해야 한다.

N~i일의 페이라고 생각하면 편하다. 미래에서 돌아온다고 생각.

다시한번 점화식의 의미를 하나하나 살펴보면 다음과 같다.

N : 문제에서 주어진 퇴사 전날

d[n] : N일부터 n일까지의 최대 페이 (n이 1이면 문제의 답이 된다)

d[n+1] : n일에 일을 하지 않았을 때의 페이. n일에 일을 하지 않았으므로 N일~n일의 페이 = N일~n+1일의 페이

d[n+T[n]] : N일~n+T[n]일까지의 페이. 

T[n] : n일에 있는 상담에 걸리는 시간

예를 들어 문제에서 주어진 대로 이렇게 표가 있다고 했을 때 (N=7)

답을 구하려면

d[1] = max(d[2], d[1+T[1]] + P[1]) = max(d[2], d[4] + 10) 이 된다.

7일~1일까지의 최대 페이를 구하려면

7일~2일까지의 페이 + 1일에는 쉼

7일~4일까지의 페이 + 1일에 맡은 상담을 함(10원을 받음)

둘 중에 큰 것을 선택해야 하기 때문이다.

+ 추가 설명

d[n] = max(d[n+1], d[n+T[n]] + P[n])

n일에 일을 하지 않은 게 d[n+1]이라는 건 이해하기 쉬운데,

일을 한 것이 d[n+T[n]] + P[n] 이라는 게 이해가 잘 되지 않았다. 일단 괄호가 많아서 눈에 잘 들어오지도 않는다.

풀어서 말하면 d[n + 상담일수] + n일의 상담 페이 라는 뜻이다. 

점화식 우변 max()에 안에 있는 두 값을 그림으로 다시 보자. 이번엔 n 대신 a를 써 보자.

이게 a일에 일을 하지 않았을 때를 의미하는 d[a+1]다.

빨간색은 그 사이에 벌어들인 돈이다. a일에 일을 하지 않았으므로 0원+d[a+1]이다.

이건 d[a+T[a]] + P[a] 이다. 그림 순서대로 보면 P[a] + d[a + T[a]] 이다.

마찬가지로 빨간 글씨는 페이, 그 사이 벌어들인 돈이다. 

뒤에 있는 파란 네모는 d[a + T[a]] 인데,

아직 모르므로 재귀를 호출해서 알아낼 수 있을 때까지 간 다음, 다시 d[1]로 돌아오면 답을 알아낼 수 있다.

(알아낼 수 있을 때까지=d[N]이다)

https://www.acmicpc.net/problem/12865

다이나믹 프로그래밍을 풀 때는 표를 그리는 경우가 많았다.

표를 그린다는 것 = 컴퓨터로 생각하면 Memoization이기 때문인 것 같다.

표를 그려보고, 그 표를 컴퓨터가 만들어낼 수 있도록 일반화하는 것이 중요하다.

하지만 정답을 해결할 수 있는 표를 만들어 낼 수 있다면 이미 그 문제를 풀 수 있다는 뜻이겠지...

그러니까 어떤 경우를 순회하면서 무엇을 저장해야 하는가? 메모이제이션 아이디어를 생각하는 게 쟁점이다.

이 문제도 마찬가지이다.

지금까지 for문을 돌렸기 때문에 무작정 for문으로 시작하려 한다면 애먹을 가능성이 높다. (내가 그랬다.)

for문으로 해결하면 안 된다는 뜻이 아니라,

먼저 '표'와 같은 해결 방법을 찾아야 한다는 뜻이다.

소스코드는 아래와 같지만,

아이디어를 이해한다면 사실 소스코드는 직접 만들 수 있을 것이고

나중에 경계값 처리 등을 실수했을 때나 보면 된다.

import sys
N, K = map(int, sys.stdin.readline().split())  # N은 물건 갯수, K는 최대 무게
item = []  # 입력으로 주어질 아이템 무게/가치 리스트
for i in range(N):
    item.append(list(map(int, sys.stdin.readline().split())))
W, V = 0, 1  # item 리스트에서 무게를 0, 가치를 1로 가리키면 헷갈리므로 그냥 이렇게 쓸 것이다

knapsack = [[0 for _ in range(K+1)] for _ in range(N)]  # 최대 가치를 저장한 표. 문제 해결의 열쇠

for index, wv in enumerate(item):
    for weight in range(1, K+1):
        if wv[W] > weight:
            knapsack[index][weight] = knapsack[index-1][weight]
        else:
            knapsack[index][weight] = max(knapsack[index-1][weight], wv[V] + knapsack[index-1][weight-wv[W]])

print(max(map(max, knapsack)))

https://suri78.tistory.com/2

를 참고했다. 표를 그리면서 설명을 잘 해놓으신 것 같다.

https://www.acmicpc.net/problem/1912

원트에 풀었지만 다시 생각해보니 생각해볼 만한 점이 있어 포스팅한다.

처음에 생각한 점화식은

이번에 들어가야 할 값 = max(이전까지의 연속합+현재값, 현재값, 현재값+바로 이전 값)

이었다.

왜 현재 값+바로 이전 값을 계산해야 된다고 생각했는지는 잘 모르겠다.

무조건 2개를 선택해서 연속합을 만들어야 한다면, 그렇게 될 것 같다.

하지만 문제에서는 1개 이상만 선택하면 된다고 했으니, 점화식은

이번 연속합 = max(바로 이전까지의 연속합+현재값, 현재값) 이 된다.

이 뜻은,

현재 값에 연속합을 더하는 것이 낫냐? 아니면 이전 연속합을 더하는게 손해냐? 를 묻는 것이다.

예를 들어 주어진 수열이 -1, -1, 55 이라고 생각할 때,

연속합+현재값은 53이고 현재 값은 55이므로 최대 연속합은 55이다.

이전 연속합들을 데리고 갈지, 아니면 더하면 오히려 손해이므로 버리고 갈 지를 결정한다고 생각하면 된다.

주석친 곳을 보면 

maxSum = max(seq[now]+subsum[now-1], seq[now]) 라고 되어 있는데, 이것이 볼드처리한 점화식과 같다.

seq는 주어진 수열, subsum은 연속합을 저장한 배열이다.

하지만 이 max 를 보면, seq[now]가 양쪽에 공통되어 있다는 사실을 알 수 있는데.

그렇다면 max(subsum[now-1], 0)이 된다.

이것을 풀어서 생각해보면 

이전까지의 연속합이 0을 넘느냐? 이다.

이전까지의 연속합이 0을 넘으면, 현재 값이 양수든 음수든 무조건 더하는게 이득이므로 데리고 간다. 라는 뜻이다.

그래서 본문과 같이 if문으로 바꿔봤더니 속도가 더 빨라졌다.

import sys
N = int(sys.stdin.readline())
seq = list(map(int, sys.stdin.readline().split())) # 주어진 수열
subsum = [seq[0]]  # 연속합을 저장할 리스트

for now in range(1, N):
    # 연속 합에 현재 값을 더하는 게 낫냐? OR 현재 값에서 다시 시작하는 게 낫냐?

    #maxSum = max(seq[now]+subsum[now-1], seq[now])
    #subsum.append(maxSum)

    if subsum[now-1] > 0:
        subsum.append(seq[now] + subsum[now-1])
    else:
        subsum.append(seq[now])


print(max(subsum))

https://www.acmicpc.net/problem/2565

선행문제: 11053번

LIS 기초 문제인 11053번을 풀어봤다면 어려울 것이 없는 문제이다.

뭔가 복잡할 것 같지만, 어느 순간에 전깃줄이 교차하는지를 생각해보면 된다.

전깃줄은 '다른 애들이 증가하고 있는데 혼자 감소하면' 교차한다.

즉, 다른 애들은 증가하고 있는데 지들만 감소하고 있는 아이들을 찾으면 되는데,

이것은 가장 긴 부분 증가 수열을 뺀 나머지들이다. (증가수열에 속하지 않으면 감소하는 애들일 것이므로)

파이썬 코드이다.

import sys
import operator

numCable = int(sys.stdin.readline())
cable = []

for i in range(numCable):
    start, end = map(int, sys.stdin.readline().split())
    cable.append([start, end])  # start는 왼쪽 전봇대, end는 오른쪽 전봇대
cable.sort(key=operator.itemgetter(0))  # 기준을 왼쪽으로 삼고 정렬한다. 

increasing = [1]  # 각 원소마다 증가 부분 수열 갯수를 저장

for now in range(1, numCable):
    candidates = [0]
    for before in range(now):
        if cable[before][1] < cable[now][1]:
            candidates.append(increasing[before])
    increasing.append(max(candidates)+1)

maxIncreasing = max(increasing)
cableToCut = numCable-maxIncreasing
print(cableToCut)

https://www.acmicpc.net/problem/11054

11053번 응용 문제이다.

어렵사리 풀긴 했는데, 인터넷에 많이들 푼 방법과는 조금 다르다.

역시 알고리즘 풀 때는 뒤집어서 생각해볼 필요가 있는 것 같다.

내가 푼 방법은 다음과 같다.

바이토닉 수열 길이를 bitonicSize에 각각 증가하고 있는 사이즈, 감소하고 있는 사이즈를 넣고

for문 내부에서는 현재 보고 있는 숫자 이전의 수열들을 하나하나 검사했다.

케이스를 2가지로 나눠서 어떤 경우에 그렇게 될 수 있는지, 그에 대한 결과가 어떻게 되어야 하는지 생각해봤다.

1. 현재 보고 있는 숫자(now)가 이전 숫자(before)보다 큰 경우는

- 계속 증가하고 있던 수열의 경우이거나

- 새로 시작하는 수열의 경우이다. 그렇다면

-> bitonicSize에서 증가하는 수열의 사이즈를 upBitonicSize에 집어넣는다.

2. 현재 보고 있는 숫자(now)가 이전 숫자(before)보다 작은 경우

- 계속 감소하고 있던 수열의 경우이거나,

- 증가하고 있다가 이번에 새로 감소하는 경우이다. 그렇다면

-> bitonicSize에서 둘 중에 큰 것을 downBitonicSize에 집어넣는다.

사실 이게 맞는 건지 잘 모르겠다.

설명하기 어려운 걸 보면, 이상한 알고리즘일지도 모르겠다. ㅜㅜ

앞에서부터, 뒤에서부터 수열을 세는 방법으로 다시 풀어봐야겠다.

import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
UP, DOWN = 0, 1
bitonicSize = [[1, 1]]  # [증가중인 바이토닉 사이즈, 감소중인 바이토닉 사이즈]

for now in range(1, N):  # now: 현재 보고 있는 숫자
    upBitonicSize = [0]  # 이전 수열들의 바이토닉 사이즈를 저장할 공간
    downBitonicSize = [0]
    for before in range(now):  # before: 이전 수열들
        if A[before] < A[now]:
            upBitonicSize.append(bitonicSize[before][UP])
        elif A[before] > A[now]:
            downBitonicSize.append(max(bitonicSize[before][UP], bitonicSize[before][DOWN]))
    bitonicSize.append([max(upBitonicSize)+1, max(downBitonicSize)+1])

maxValue = 0
for i in bitonicSize:
    maxValue = max(maxValue, i[0], i[1])

print(maxValue)

https://www.acmicpc.net/problem/10844

이전까지 풀었던 단순하게 눈에 보이는 규칙 찾기로는 풀리지 않는 문제였다.

뭔가 전에 자릿수에서 그 다음 자릿수의 수들이 파생된다는 것은 알겠는데,

컴퓨터가 하는 일이므로 정확한 기준을 가지고 어떻게 파생이 되는지를 캐치했어야 했는데 그러지 못했다.

생각의 흐름은 다음과 같다. (잘못된 생각의 흐름이다)

1. 전에 풀었던 것처럼 규칙을 찾아야겠구나

2. 0은 0이고, 1일 때는 9이다. 그럼 2일 때는...(하나하나 만들어서 세어봄)

3. 자릿수가 3개인 수 중에서 계단 수를 만들어보면서 세는데, 자꾸 누락되는 게 생겼다.

4. 자릿수가 4개인 수 중에서 계단 수를 만들어보려고 했는데, 너무 양이 많아져서 이 방향이 맞는가 하고 의구심이 들었다.

5. 결국 3까지 만든 결과에서 점화식을 만들어서 풀었는데, 3까지는 적용되었지만 답은 아니었다.

문제는 수가 너무 커지는데 이를 무식하게 단순한 수열 규칙을 찾으려고 했던 것이었다.

수가 커지므로, 이를 분할해서 규칙을 찾았으면 좀더 정답에 접근할 수 있었을 것 같다.

정답의 아이디어는

자릿수가 N일 때 0으로 끝나는 계단 수, 1로 끝나는 계단 수, ....9로 끝나는 계단 수를 따로 찾는 것이다.

이를 표로 그려놓고 보면 규칙이 보인다.

양 대각선 위 방향을 더한 것이다. 0이나 9는 대각선 방향이 하나 밖에 없으므로 구현할 때는 if문으로 따로 나눠줘야 한다.

import sys

N = int(sys.stdin.readline())
cal = [[0]*10 for _ in range(N+1)]
cal[1] = [0,1,1,1,1,1,1,1,1,1]

for i in range(2, N+1):
    for lastNum in range(0, 10):  # 0부터 9까지
        if lastNum == 0:
            cal[i][lastNum] = cal[i-1][1]
        elif lastNum == 9:
            cal[i][9] = cal[i-1][8]
        else:
            cal[i][lastNum] = cal[i-1][lastNum-1] + cal[i-1][lastNum+1]

ret = 0
for i in range(10):
    ret += cal[N][i]

print(ret % 1000000000)

https://www.acmicpc.net/problem/1463

열흘 전... (인터넷에서 보고 따라한 코드)

n = int(input())
m = []  # 미리 초기화를 하면 밑부분 m[0]~m[3]을 초기화해주는 부분에서 out of index 날 수 있다
 
m.append(0)
m.append(0)
m.append(1)
m.append(1)
 
for i in range(4, n+1):
    m.append(m[i-1] + 1);
    if(i % 2 == 0):
        m[i] = min(m[i], m[i//2] + 1) 
    if(i % 3 == 0):
        m[i] = min(m[i], m[i//3] + 1) 
 
print(m[n])

이번에 풀이법이 생각나지 않을 무렵 직접 작성한 코드

import sys

N = int(sys.stdin.readline())
cal = [0 for _ in range(N+1)]  # 0은 없는 셈 친다.

if N > 1:
    cal[2] = 1  # cal[1] = 0

for i in range(3, N+1):
    tmp1 = i - 1
    tmp2 = i // 2
    tmp3 = i // 3

    if i % 2 == 0 and i % 3 == 0:
        cal[i] = min(cal[tmp1], cal[tmp2], cal[tmp3]) + 1
    elif i % 2 == 0:
        cal[i] = min(cal[tmp1], cal[tmp2]) + 1
    elif i % 3 == 0:
        cal[i] = min(cal[tmp1], cal[tmp3]) + 1
    else:
        cal[i] = cal[tmp1] + 1

print(cal[N])

시간이 100ms가 더 오래 걸렸지만, 유의미한 차이는 아닌듯하다.

하지만 코드를 봤을 때 확실히 다른데서 가져온 코드가 깔끔해보인다.

전자가 보고 따라한 코드(한마디로 퍼온 코드), 후자는 직접 작성한 코드이다.

가장 먼저, 기저 사례를 정의하는 부분이 다른데, 

전자의 경우 append를 이용해 out of index가 안나게끔 정의해준 반면

후자의 경우 2 이상일 경우에만 2를 정의하도록 했다. 사실 처음에는 if문이 없었는데, 자주 하는 실수이다.

문제에서 N이 어디부터 주어질 수 있는지 보지 않은 것이다.

문제에서는 1부터 주어질 수 있다고 했으므로, N이 1일 때도 고려해야한다.

무턱대고 cal[2]부터 정해주면 N이 1일 때 out of index 오류가 난다.

전자는 왜 하필 4부터 for문을 돌렸는지 의문이다. 직접 계산한 가능 범위라면, 5도 될 수 있고 6도 될 수 있지 않나 싶다.

후자는 3부터는 일반화된 수식이 적용될 수 있다는 생각이 들어 바로 3부터 for문을 돌렸다.

이제 for문 내부를 보자.

전자는 일단 N-1했다고 치고 그 값을 리스트에 넣고 N / 2 가 가능하다면 그 중 최솟값을 다시 넣고, N / 3이 된다면 그 중 최솟값을 다시 넣고, N / 2 와 N / 3 이 둘다 된다면 그 중 최솟값으로 또다시 수정했다.

후자는 N-1, N / 2, N / 3 한 값을 따로 구해서 그 값 중 최솟값을 넣었다.

보기에는 전자의 코드가 훨씬 깔끔해보이지만 시간 차이가 크지 않아 유의미한 차이는 없어보이고,

중요한 것은 열흘 전에 이 문제를 풀 때는 바텀업이 어쩌고 재귀가 어쩌고 했던 반면,

이번에 풀 때는 동적 프로그래밍이니 값을 저장해주면서 이건가...? 하고 쉽게 풀어갔다는 점에 의미가 있겠다.