1번 : 피보나치 수열 구하기

2번 : https://boj.kr/5463 건포도

2차원 누적합에 가능한 N^4개의 구간에 대해 메모이제이션하는 문제

재귀로 구현했는데 ac 받음

3번 : https://boj.kr/14335 서로 다른 부분 수열의 개수

c를 추가했을 때 변화량 = (현재까지 모든 부분 수열) - (c로 끝나는 부분 수열) + 1 (== “c”)

이므로 끝나는 문자에 따른 개수를 관리하면 됨

4번 : https://boj.kr/5492 Hermes

경찰차 같이 풀면 된다는데 잘 모르겠고 map에 가능한 {좌표, 거리}를 전부 때려박고

a를 깨우는 데에 필요한 거리의 최솟값 + 4000보다 거리가 큰 애들은 빼니까 통과함

(4000이면 어느 좌표로든 갈 수 있는 거리니까 최솟값인 애가 a를 깨우고 산책 갔다 오는 게 더 효율적이기 때문)

이게왜됐는지 잘 모르겟음

5번 : 못 품

주어진 열량과 나트륨 함량 이내에서 먹을 수 있는 최대의 치킨 개수를 구하는 문제

열량/함량 ≤ 5000, 개수 ≤ 100

[치킨 개수][나트륨 함량]에서 최소의 열량을 구하면 됨

6번 :

못 품

7번 : https://boj.kr/6171 땅따먹기

CHT 웰논 문제.

무료로 살 수 있는 땅을 제외하고 나면 점화식이 cht 형태로 이쁘게 나와서 cht로 풀 수 있음.

CHT를 푸는 방법을 LineContainer랑 리차오트리밖에 몰라서 리차오 트리로 ac 받음

8번 : 못 품 (업솔빙 X)

4번의 1차원 버전 같은 느낌, N이 20만으로 매우 크므로 세그먼트 트리로 최적화

라고 풀이해주셨는데 잘 모르겠다.

9번 : 못 품

10번 : 15771. Recipe (못 품, 업솔빙 성공)

i일에 산 식재료를 사용했을 때 i~n일 최대 맛을 dp[i]라 하면

dp[i] = max(c[j] * (f[i] + i) - c[j] * j + dp[j+1]) (i ≤ j && L[j]+j ≤ F[i]+i)

얘는 누가 봐도 cht 꼴이다. 그리고, 반직선의 범위가 [(l[i]+j) , $\infin$) 임을 관찰할 수 있다.

리차오 트리를 써서 해결.

반직선의 범위에 관한 관찰을 못 해서 자력으로는 20점까지 받을 수 있었다.

11 : Dango Maker ( 못 품, 업솔빙 성공 )

대각선으로 G만 봤을 때 인접한 G는 방향이 같아야 둘 다 가능 ⇒ 대각선 방향으로 dp

업솔빙 성공. 깔끔하게 짜서 기분이 좋다

12 : Redistricting

풀었거나 업솔빙 성공한 문제의 코드는 깃허브에 있습니다.

난이도별로 분류되어 있어서 문제 번호로 검색하시면 편함