Awesome

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 한 값을 따로 구해서 그 값 중 최솟값을 넣었다.

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

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

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

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

예시를 그대로 갖고왔다.

5번째 계단은 무조건 밟아야 한다.

그럴 때 최댓값은, 5번째 계단의 점수 20을 더한 상태에서 

4번째 계단을 선택했을때이거나

3번째 계단을 선택했을 때이다.

4번째 계단을 선택하려면 3번째 계단은 선택하면 안 된다. (3개 연속 밟을 수는 없으므로)

3번째 계단을 선택하려면 2, 1번째 계단 중 어떤 것을 선택해도 상관 없으며 최댓값을 고르면 된다. 

val은 바로 전 계단을 선택했을 때의 최댓값을 R, 

전전 계단을 선택했을 때의 최댓값을 F로 해서 두 값을 모두 담았다. 나중에 최종적으로 둘 중에 최댓값을 고를 것이다.

이를 정리해보면

N번째 계단에서의 최댓값은 일단 N번째 점수를 더한 상태에서 (stair[col])

N-1번째를 선택하되 N-1은 바로 전 계단이 아닌 전전 계단을 선택한 상태거나 (val[col-1][F])

N-2번째를 선택하고 N-2가 바로 전 계단을 선택했거나, 전전 계단을 선택했을때의 두 점수 중에서 최댓값을 고르는 것이다. (max(val[col-2][F], val[col-2][R])

쉽게 설명하면 F는 Front로 "앞에꺼, 즉 -2번째 계단을 선택한 상태" , R은 "뒤에꺼, 즉 -1번째 계단을 선택한 상태"로 보면 된다.

내가 풀었지만, F, R이라는 단어를 잘못 선택한 것인지 쉽게 설명하기가 영 어렵다.

그림 그리면서 F는 전전 거를 선택한 상태, R은 전 거를 선택한 상태라고 생각하면 조금이나마 쉽다..

미래의 나에게 하는 이야기.

import sys


def solve():
	dp = []
	dp.append([stair[0], stair[0]])  # dp[0]

	for i in range(1, N):
		if i == 1:
			dp.append([stair[0]+stair[1], stair[1]])
		else:
			walk = dp[i-1][JUMP] + stair[i]
			jump = max(dp[i-2]) + stair[i]
			dp.append([walk, jump])
				
	print(max(dp[N-1]))


WALK, JUMP = 0, 1  # 그 전 계단을 걸어온경우, 점프한경우
input = sys.stdin.readline
N = int(input())

stair = [int(input()) for _ in range(N)]

solve()

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

선행 문제인 RGB거리 문제를 풀었다면 쉽게 해결할 수 있는 문제였다.

추상화가 필요없다는 점에서 이게 더 쉬운 것 같기도...

마찬가지로 이전 행까지의 값을 저장해놓고 있어야 하기 때문에 동적 프로그래밍에 해당하는 문제이다.

bottom-up으로 찾고 싶은 높이까지 최댓값을 각각 열마다 저장해나가는 것이 포인트다.

파이썬이기 때문에 삼각형 모양의 배열 선언이 비교적 쉬웠던 것 같다.

import sys
n = int(sys.stdin.readline())
tri = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
val = [[0]*i for i in range(1, n+1)]

val[0][0] = tri[0][0]

for row in range(1, n):
    if row == 1:
        val[1][0] = tri[1][0] + val[0][0]
        val[1][1] = tri[1][1] + val[0][0]
    for col in range(row+1):
        if col == 0:  # 제일 첫 번째
            val[row][0] = tri[row][0] + val[row-1][0]
        elif col == row:  # 제일 마지막번째
            val[row][-1] = tri[row][-1] + val[row-1][-1]
        else:  # 그게 아닌, 대각선 방향 두 개 중에 선택해야 하는 것들
            val[row][col] = tri[row][col] + max(val[row-1][col-1], val[row-1][col])

print(max(val[n-1]))