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)

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

참고로 문법은 python2, 제출은 pypy2로 했다.

python3으로 하니 시간 초과가 났다.

주요 아이디어는 zero라는 리스트에 값이 0인 것들의 행렬을 튜플로 저장해놓은 것이고,

또 작은 사각형에 중복된 숫자가 있는지 검사할 때

속하는 작은 사각형의 범위를 (row//3)*3, (col//3)*3으로 표현한 것이다.

이것만이 정답은 아니지만 프로그래밍을 할 때

'무언가 정보를 담을 새로운 공간'를 떠올려 보는 것도 좋을 것 같다.

import sys
r = sys.stdin.readline

board = []
for i in range(9):
    board.append(list(map(int, r().split())))

zero = []
for i in range(9):
    for j in range(9):
        if board[i][j] == 0:
            zero.append((i, j))

def Print():
    for row in range(9):
        for col in range(9):
            print board[row][col],
        print("")

def isPossible(num, row, col):
    if num in board[row]:
        return False
    for i in range(9):
        if num == board[i][col]:
            return False
    row_t = row // 3 * 3
    col_t = col // 3 * 3
    for r in range(row_t, row_t + 3):
        for c in range(col_t, col_t + 3):
            if num == board[r][c]:
                return False
    return True

def dfs(zeroIndex):
    if zeroIndex == len(zero):
        Print()
        exit(0)
    for num in range(1, 10):
        row = zero[zeroIndex][0]
        col = zero[zeroIndex][1]
        #print("row col: {} {}".format(row, col))
        if isPossible(num, row, col):
            board[row][col] = num
            dfs(zeroIndex+1)
        board[row][col] = 0

dfs(0)

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

앞선 문제인 N과 M에서 사용되는 DFS를 활용한 문제이다.

중요한 아이디어는 같은 row에는 퀸이 하나밖에 존재할 수 없으며, 또 하나는 무조건 있다는 것이다.

이번 row에는 퀸이 어디에 와야할 지 column을 차례대로 늘려가면서 findColumn 함수를 통해 검사한다.

개인적으로는 row와 col이 서로 헷갈리고, for문의 range를 정하는 것 때문에 어려웠던 문제이다.

코드 설명은 주석으로 대신한다. 밑에서부터 보면 된다.

def isPossible(row, col):  # 위 혹은 양방향 대각선에 퀸이 있는지 검사
    # 좌우는 볼 필요가 없다. 하나의 row에는 하나의 퀸!

    # 위 (아래를 안 보는 이유는 아직 다음 row 자체를 안 봤기 때문
    for i in range(1, n):  # 주의: 1부터다. 0으로하면 7번째 줄에서 자기 자신과 같은지 검사하게 됨
        if row-i >= 0:  # row를 1씩 줄여가되 음수가 되지 않도록 한다. 
            if chess[row-i][col]:  # 퀸을 발견했다
                return False

    # \ 방향 대각선. row, col에서 1씩 빼면서 확인
    for i in range(1, n):
        if row-i >= 0 and col-i >= 0:
            if chess[row-i][col-i]:
                return False

    # / 방향 대각선. row는 -1, col은 +1 (그림으로 생각해보자)
    for i in range(1, n):
        if row-i >= 0 and col+i < n:
            if chess[row-i][col+i]:
                return False
    return True  # 위 모든 검사를 통과했다면 그거슨 퀸

def findColumn(row):
    global answer  # 전역변수를 함수 내에서 수정하기 위해 global 선언
    if row == n:  # 하나의 row에는 하나의 퀸이 무조건 들어가므로, row가 n이라면 퀸의 자리를 다 찾은 것임
        answer += 1
        return
    for col in range(n):  # row는 정해져 있으니 column을 1씩 증가시키면서 확인한다
        if isPossible(row, col):  # 놓을 수 있다면 
            chess[row][col] = True  # True로 퀸의 자리를 표시
            findColumn(row+1)  # 다음 row에서 퀸의 자리를 찾는다
        chess[row][col] = False  # 재귀가 끝난 후, 백트래킹해야하므로 다시 False로 돌려놓는다

n = int(input())
chess = [[False]*n for _ in range(n)]  # 체스판. True면 퀸이 있는 자리
answer = 0
findColumn(0)  # 인자는 row. 0번째 row부터 퀸이 들어갈 column을 찾는다.
print(answer)