0. 서문
몸이 한계인건지 뭔지 너무 졸립고 머리가 아프다. 그 탓인지 진도가 잘 안나가는것도 상당히 괴로운 부분이었다.
이번주에 하는것이 DP 다 보니 DP 에 대한 이야기를 이것저것 듣게 되었는데 그중 기억나는 몇가지를 적어보려 한다.
-
코테에서 DP 유형이 나오면 그냥 넘겨라. 보고서 그날 컨디션 좋고 해서 바로 점화식 보이면 푸는거고 아니면 다른거 푸는거다.
-
"점화식을 알면 DP를 쉽게 짤 수 있는데 점화식을 어떻게 만들지 모르겠다"라고 하시는 분들 계실텐데, 맞습니다. 점화식을 만드는 것 자체가 문제를 푸는 것이고, 좀 더 정확하게는 문제를 어떻게 잘 자를 수 있는가를 찾는 과정입니다. 사실 1주차 재귀, 2주차 분할정복에서부터 필요했던 능력입니다.
-
가끔 보면, 문제를 딱 보고 어떻게 자르면 되는지 알아차리기를 원하시는 분이 계시는데, 그 정도의 능력은 저는 재능의 영역으로 봅니다. 솔직히 이게 되면 못 풀 문제 없죠. 특정 사람들만 알아듣는 말로 "직사의 마안"을 가졌다고 표현합니다. 그렇다고, 노력해도 기를 수 없는 능력이냐 하면... 뭐, 하다 보면 늘기는 합니다.
아무리 생각해도 나한테 직사의 마안은 없으니 그냥 계속 하면서 늘리는걸로...ㅎㅎ
추가로 DP 랑은 상관없이 우연히 걷다가 코치님을 만나서 듣게 된 이야기도 적어두려한다.
"문제를 못풀었다고 할 때 남이 쓴 코드를 봤다고 해서 못 푼 것이 아니다. 이 코드를 보고 이해하고 다시 자기가 그 코드를 짜고 설명할 수 있다면 그 문제는 푼 것이다. 반대로, 코드를 보고 이해만 하고 넘어가서 그 문제를 풀지 못한다면 그 문제는 풀지 못한 것이다."
세세하게 따지자면 다르긴 해도 핵심적으로는 이렇게 말씀하셨다. 확실히, 코드를 보고 이해만 하지 말고 내가 스스로 짤 수 있게 해야겠다는 생각이 들었던 말씀이었다.
AKMU (악뮤) - 낙하 (NAKKA) (with IU)
1. 행렬 곱샘 순서
https://www.acmicpc.net/problem/11049
파이썬으로 배우는 알고리즘 기초: 11. 연쇄 행렬 곱셈
해당 영상을 보면서 계속 반복해서 이해할려고 했던 문제였다.
그렇게 해서 이해했냐고 하면 글쎄...솔직히 단번에 이해하기 힘든 문제라 생각하면서 접근하긴했지만 강의를 듣고 코드를 보고 해도 솔직히 잘 모르겠는 문제다. 솔직히 말해서 어떻게 원리는 알것도 같은데...
pypy 3 로 제출하였다.
import sys
input = sys.stdin.readline
INF = 2e9
n = int(input())
A = [list(map(int, input().split()))]
for _ in range(n):
r, c = map(int, input().split())
A.append((r, c))
dp = [[INF for _ in range(n)] for _ in range(n)]
for i in range(n):
dp[i][i] = 0
for i in range(n-1, -1, -1):
for j in range(i+1, n):
dist = j-i
for k in range(dist):
dp[i][j] = min(dp[i][j], dp[i][i+k]+dp[i+k+1]
[j]+A[i][0]*A[i+k][1]*A[j][1])
print(dp[0][-1])2. 가장 긴 증가하는 부분 수열
https://www.acmicpc.net/problem/11053
인프런에서 들었던 강의에서 풀었던 소스코드를 그대로 제출하니 한 80 까지는 정답이더니 확하고 틀려버렸다. 언제나 그렇듯이 이러한 케이스가 가장 답답하다. 처음부터 틀리면 모를까 중간부터 틀리고 예시도 다 맞으니 어찌해야할지 생각이 안나서 더 막막한 케이스.
결국 다른 사람의 답을 보고말았다. 크게 차이가 없던것 같기는 한데 왜 내껀 안됬던건지...
import sys
input = sys.stdin.readline
n = int(input())
number = list(map(int, input().split()))
dy = [0] * n
for i in range(n):
for j in range(i):
if number[i] > number[j] and dy[i] < dy[j]:
dy[i] = dy[j]
dy[i] += 1
print(max(dy))3. 단어 공부
https://www.acmicpc.net/problem/1157
따로 공부할려고 한건아니고 조금만 더 풀면 백준 골드 3 이 되길래 브론즈 조금 풀고 올리려니까 브론즈 문제로는 턱도 없는지 3개정도 풀어서는 경험치 1도 오르지가 않더라. 아니면 브론즈 문제로는 레벨업이 안되던가...
import sys
n = int(input())
number = list(sys.stdin.readline().rstrip())
hap = 0
for i in range(n):
hap += int(number[i])
print(hap)4. 음계
https://www.acmicpc.net/problem/2920
arr = list(map(int, input().split()))
number = [1, 2, 3, 4, 5, 6, 7, 8]
re_number = [8, 7, 6, 5, 4, 3, 2, 1]
if arr == number:
print("ascending")
elif arr == re_number:
print("descending")
else:
print("mixed")
5. 숫자의 합
https://www.acmicpc.net/problem/11720
import sys
n = int(input())
number = list(sys.stdin.readline().rstrip())
hap = 0
for i in range(n):
hap += int(number[i])
print(hap)
