Awesome

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

처음에는 이게 왜 동적 프로그래밍인지 모르겠어서 해결방법이 보이질 않았다.

현재 R을 선택했을 때와 G, B를 선택했을 때의 결과를 각각 따로 저장해야된다고는 생각했는데

막연히 생각하기에 그렇게 하면 시간이 너무 오래 걸릴 것 같았다.

하지만 그렇게 해도 한 번 돌 때마다 3개의 계산을 한꺼번에 하므로, N의 시간밖에 걸리지 않는다는 것.

for문 안쪽의 의미는 다음과 같다.

• i번째에 R 색깔을 칠했을 때의 누적 비용 (0~i-1까지 무언가를 칠하고, i번째에 R을 칠했을 때의 모든 비용) =
• i번째에 R색깔을 칠하는 데 드는 비용 (이번만 칠하는 데 드는 비용) +
• i-1번째에서 G 혹은 B 색깔로 칠하는데 들었던 비용 중 최솟값(이 값 역시 누적된 비용이다)

import sys
N = int(sys.stdin.readline())
cost = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 입력(색칠비용)
val = [[0,0,0] for _ in range(N)]  # 계산될 색칠 비용 결과
R = 0
G = 1
B = 2

val[0][R] = cost[0][R]
val[0][G] = cost[0][G]
val[0][B] = cost[0][B]

for i in range(1, N):
    val[i][R] = cost[i][R] + min(val[i-1][G], val[i-1][B])
    val[i][G] = cost[i][G] + min(val[i-1][R], val[i-1][B])
    val[i][B] = cost[i][B] + min(val[i-1][G], val[i-1][R])

print(min(val[N-1][R], val[N-1][G], val[N-1][B]))  # 0부터 시작이므로 N-1

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

import sys

'''
chosen 리스트에 담긴 순서대로 계산하는 함수
0: +, 1: -, 2: *, 3: / 로,
chosen에 0, 0, 1, 2, 3이 담겨있다면 연산자 순서는 + + - * / 이 된다.
그리고 numbers와 chosen에서 하나씩 꺼내오면서 계산 후 결과를 리턴 
'''
def calc():
    ret = numbers[0]  # 일단 첫번째 숫자를 결과에 넣고 시작
    for idx, op in enumerate(chosen):
        if op == 0:
            ret += numbers[idx+1]
        elif op == 1:
            ret -= numbers[idx+1]
        elif op == 2:
            ret *= numbers[idx+1]
        else:
            if ret < 0:
                ret = -(abs(ret) // numbers[idx+1])  # 문제에 있던 c++14 스타일 음수 나눗셈
            else:
                ret = ret // numbers[idx+1]
    return ret


'''
연산자의 종류는 총 4개이므로, 4번을 for문으로 돌되 
선택된 연산자는 oper 리스트에서 1씩 빼 준다. 0이 되면 그 연산자를 패스한다.
순열과 똑같다.
'''
def dfs(count):
    global minValue, maxValue
    if count == sum:
        minValue = min(minValue, calc())
        maxValue = max(maxValue, calc())
        return
    for i in range(4):
        if oper[i] <= 0:
            continue
        oper[i] -= 1
        chosen.append(i)  # 0-더하기,1-빼기,2-곱,3-나누기
        dfs(count+1)
        chosen.pop()
        oper[i] += 1


n = int(sys.stdin.readline()) # 숫자의 갯수. 문제에서의 n
numbers = list(map(int, sys.stdin.readline().split()))  # 숫자 리스트
oper = list(map(int, sys.stdin.readline().split()))  # 입력 받는 연산자 배열. ex) 0 1 0 0
sum = 0  # 입력 받은 oper 리스트의 합. 이제 연산자 선택을 다 했으니 계산해라~할 때 조건문에 쓰임
for i in oper:
    sum += i
chosen = []  # 선택된 연산자
ret = 0  # 각 케이스 별 계산 결과를 담을 변수
minValue = 1000000000  # 주의! 0으로 초기화하면 min이 0이 되어버릴 수 있음
maxValue = -1000000000
dfs(0)
print(maxValue)
print(minValue)