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

수열에서 연속 부분 수열 두개를 골라 그 곱이 가장 클 때 얼마나 클지 알아내야 한다.

연속 부분 수열이 얼마나 클지를 알아내는 방법은 디피 문제를 풀 때 쉽게 접할 수 있는 문제다.

dp[x]를 x번째 인자를 포함한 부분 수열 중 합이 가장 큰 수를 저장하게 정의해 놓으면,

dp[x]는 dp[x-1]이 음수인 경우와 양수인 경우로 나눠 원타임에 값이 정해진다.

또한 새로운 디피 배열 lmax를 정의할 수 있게 되는데,

이번엔 lmax[x]는 x번째 인자를 반드시 포함하지 않아도, x까지 수열의 부분 수열 중 합이 가장 큰 수를 저장한다고 정의해 놓으면,

lmax[x] = max(lmax[x-1], dp[x])로 원타임에 값이 정해진다.

즉 x가 포함되던지 안되던지 두 케이스 중 큰 값으로 정해지는 것이다.

이를 응용해서 왼쪽에서 부터, 오른쪽에서 부터, 최대합 부분수열, 최소합 부분수열을 모두 n타임에 구할 수 있다.

그러고 난 다음 부분 수열 두 개로 나눌 기준점을 n개 중에 골라서 비교하는 작업도 n타임에 수행할 수 있다.

캥거루 세마리

세 마리가 동일한 지점에 있다면 항상 같은 결과가 나온다는 생각으로, dp를 시도해 볼 수 있다.

점프 이후 전에 계산했던 상황이 나오면 재활용 할 수 있는 것이다.

각 상황은 세 마리의 위치로 구분되므로, dp[100][100][100]으로 조질 수 있다. 최악의 경우 백만번의 연산을 수행한다.

재귀적으로 왼쪽, 오른쪽 캥거루가 움직일 경우에 최대 점프수를 알아내서, 그 중 최대값에 1을 더해주면 답이다.

포도주 시식

1로 만들기

디피로 완전탐색하자.

덜 논리적이라 디피는 재귀로 풀곤하는데(2)(완전 거의 대부분) 포문풀이(1)와 속도 차이가 4배정도 난다.

또한 재귀적으로 나누기 3의 상태를 보는게(3) 더 빠르다. 아마 더 빨리 1에 가까워져서가 아닐까 싶다

(1)

(2)

(3)

계단 오르기

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

계단을 오르면 점수를 얻는다. 도착지점 까지 일련의 규칙으로 올라갈 때, 얻을 수 있는 최고점은 얼마일까?

도착지점에서 생각해보면, 이 지점에 오기 위해서는 두 계단 밑이나, 한 계단 밑에서 올라왔을 것이다.

또한 그 지점 자체의 최고점이 존재할 것이며, 그 최고점은 두 계단 밑이나 한 계단 밑에서 올라오면서 형성된다.

따라서 각 층마다 상태를 dp로 저장해서 풀면 되겠다.

유의할 점은 한계단씩 연속으로 두번 오를 수 없다는 점이다.

즉 한번 한 계단만 올랐으면, 다음엔 반드시 두 계단을 올라야 한다.

그러면 한 층에서 상태는 두가지로 나눠지고 O(n * 2) 안에 풀 수 있다.

함수 func(int floor, int cnt) = floor층이고, 한 계단씩 연속해서 cnt번 올라왔을 때 얻는 최고점수를 계산해줌.

다음 층으로 오를 때는 cnt = 1이라면 2층 오르는 상태로 이어지며,

cnt = 0 이라면 한 계단 오르거나 두 계단 오르는 상태로 분기된다.

RGB거리

2342. Dance Dance Revolution

1 2 2 4 0

8

1. 접근

발의 위치가 5가지 혹은 4가지로 좁힐 수 있으니 뭔가 그리디 하게 풀 수 있을까 생각이 든다.

하지만 빡대가리로는 직관적인 그리디 방법이 떠오르지 않으므로 만만한 다이나믹 프로그래밍으로 완전탐색 해보자.

2. 풀이

항상 다이나믹 프로그래밍으로 풀 땐 dp배열을 잘 정의해야한다.

어떻게 정의하느냐에 따라 시간복잡도가 달라지고 시간제한에 걸릴지 말지 판가름 할 수 있기 때문이다.

두 발로 와리가리 하는걸 보니 왠지 경찰차 문제 http://js1jj2sk3.tistory.com/52 가 떠오르긴한다.

당시 dp배열은 dp[경찰차 1이 마지막으로 처리한 사건 번호][경찰차 2가 마지막으로 처리한 사건 번호]로 정의했었다.

사건은 천개가 맥시멈이니까 백만 안으로 들어오는 dp배열이 가능했었다.

이 방법으로 이 문제도 조질 수 있을까?

ddr 노트가 십만가 들어온다니까 불행히도 불가능하다.

그래서 내 생각으로는 일단 몇번째 노트 짼지는 기억해야 하니까 십만칸은 기본적으로 필요하다.

또한 직관적으로 왼발 오른발의 상태를 나타내야하니 5 * 5 = 25 칸도 필요하다.

그래서 걍 25 * 십만칸으로 조지기로 하자. 이래버리면 20 MB 정도 써야한다 ㅜㅜ

(분명히 더 나은 방법이 있다. 맞은사람들을 보면 1MB 쓴 사람도 있다.)

그래서 dp[왼발 위치][오른발 위치][다음에 밟을 노트가 몇번째] 로 정의하고 나면

함수는 func(int l, int r, int i) = 현재 상태가 이러저러 할 때 앞으로 힘을 얼마나 더 써야하는지 최소량으로 정의된다.

함수의 기저사례는 i가 끝까지 가버려서 게임을 다해버린 경우다.

아니라면 두 발의 상태에 따라 함수가 다르게 확장된다.

먼저 두 발이 중앙에 있었다면, 다음 노트에 따라 왼발을 옮기든지 오른발을 옮기든지 하면 된다.

따라서 두 경우를 구해보고 최소값을 리턴하자. 

하지만 잘 생각해보면, 무조건 왼발/오른발을 옮겨도 똑같은 결과다.

다음 경우는 다음 노트가 내 두발 중 하나랑 겹치는 경우다.

이 때는 발은 그대로고 힘을 1만큼 쓰기만 하면 된다.

마지막 경우는 완전 새로운 노트로, 왼발을 옮길지, 오른발을 옮길지 따져봐야 한다.

또한 발을 옮길 때 힘을 다르게 쓰므로 주의하자.

중앙에서 옮기면 2을, 반대편으로 가면 4를, 아니면 3만큼의 힘을 쓴댄다.

3. 코드

4. 후기

재귀질이니까 바텀업보다 메모리도 시간도 더 쓰긴한다. 코드를 좀 더 간결하게 써서 시간을 최대한 줄여보자.

2618. 경찰차

6
3
3 5
5 5
2 3

9
2
2
1

1. 접근

그리디로는 풀 수 없다. 당장 가까운 경찰차를 보낸다고 하면, 남은 문제는 방금 푼 문제의 조건과 달라지기 때문이다.

그러면 당연히 다이나믹 프로그래밍으로 다 해봐야 한다!

2. 풀이

배열을 어떻게 잡아야 시간안에 풀 수 있을까? 즉, 공통된 계산부분을 잘 만들어내야한다.

모든 경우을 빡대가리처럼 다 계산해버리면 2 ^ 1000 만큼 계산해야 한다.

그럼 무엇이 공통된 사건일까? 중요한건 당연히 현재 경찰차 두대의 위치다.

사건 순서대로 경찰차가 출동한 순서를 예를들어 1->1->2->1->1 이라 해보자. 어쨌건 다섯번 출동하고 나서의 경찰차 두대의 위치는 2->1->2->1->1 와 같다. 경찰차 1은 다섯번째 사건위치에 있을 것이며, 경찰차 2는 세번째 사건위치에 있을 것이다.

그러면 우리는 dp배열을 다음과 같이 정의할 수 있다. dp[x][y] = 현재 경찰차 위치가 x, y 일 때 남은 최소이동거리.

문제는 지금까지 몇번 출동했는지를 모른다는 점이다. 하지만 경찰차 위치는 {1,1} 아니면 {n,n} 아니면 사건위치 이므로, 간략히 0~n 까지의 번호가 부여된 위치로 대체할 수 있다. 동시에 지금까지 얼마나 사건을 처리했는지도 알 수 있다.

따라서 dp[x][y] = 현재 경찰차가 가장 최근에 처리한 사건이 x, y 일 때 남은 최소이동거리. 라고 정의한다.

max(x,y) = k 라면 지금까지 k번째 사건까지 출동했다는 이야기가 된다. 그러면 이제 k+1 사건에 대해 두 대를 출동시켜보고 최소인 경우로 리턴해주면 되겠다.

문제에서 요구하는 답은 추가적으로 사건마다 어떤 경찰차가 출동했는지도 출력해야 한다. 어떻게 알 수 있을까?

dp배열을 갱신하면서 값을 알 수 있는 방법도 분명있다. (하지만 내가 빡대가리라 따로 구하기로 한다.)

dp배열을 모두 갱신하고 나면, 각 칸마다의 정보를 이용해서 어떤 경찰차가 출동했는지 알 수 있다.

만약 dp[1][2] = 10 이고, 확장되는 두 가지 dp[1][3] = 7, dp[3][2] = 5 라면, 당연히 1번 차를 출동시켜 3번 사건을 맡게 했다는 뜻이다.

모든 경우에 대해 이미 계산이 끝났으므로, 사건 수만큼 재귀를 돌고 어떤 차가 출동했는지 알 수 있다.

3. 코드

2098. 외판원 순회

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

4
0 10 15 20
5  0  9 10
6 13  0 12
8  8  9  0

35

1. 접근

DP로 완전탐색 하자

2. 풀이

모든 방문경로를 dp 배열에 담으려면 dp를 어떻게 정의해야 할까?

일단 한 번 방문한 도시로는 돌아가지 않으니까(사이클 없슴) 마지막으로 방문한 도시로 경로를 일단 나눠볼 수 있다.

하지만 이것만으로는 부족하니까 지금까지 어떤 도시를 방문했는지를 기억해야 한다.

따라서 1->3->4->2 와 1->4->3->2 는 같은 dp칸에 담기겠지만, 두 경로 중 최소값이 dp에 담길 것이므로 문제에 적합하다.

dp[cur][stat] = 현재 내위치가 cur이고, 지금까지 stat의 도시들을 방문했을 때 최소값.

stat을 비트로 표현한다면 적당하다. 0이면 미방문이고, 1이면 방문했다.

예시의 경우 dp[2][000...1111]이 되겠다.

이제 dp를 채워줄 함수를 정의해보자.

func(int cur, int stat) = dp[cur][stat]을 계산해준다.

다음 지점을 방문할 때 계산은 어떻게 해야할까?

stat을 보고 해당비트가 0인 도시에 대해 함수를 콜하면 되겠다.

3. 코드

4. 후기

방문안한 지점중에 최소값을 찾는 부문에 무턱대고 int m = INT_MAX 을 써버렸더니 틀려버렸다..

생각해보니 포문을 돌고나도 여전히 INT_MAX라 리턴해버리면 다른데가서 cost가 더해져버리고 엉망이 되는 경우가 있었다.

빡대가리

1937. 욕심쟁이 판다

4
14 9 12 10
1 11 5 4
7 15 2 13
6 3 16 8

4

1. 접근

이차원 배열이 주어지고, 팬더는 아무 지점에서나 시작할 수 있다. 팬더의 이동은 상하좌우의 배열값에 따라 가능한데, 이웃의 배열값이 현재값보다 클 경우에 이동할 수 있다. 모든 이웃지점으로 이동할 수 없다면 팬더는 죽는다!

이러한 조건하에, 팬더가 최대한 오래 살 수 있는 일수는 얼마일까?

= 팬더가 최대한 오래 이동할 수 있는 경우는 무엇일까?

직관적으로 모든 지점에 대해 DFS를 돌려보고 최대값을 구할 수 있겠다.

하지만 한 지점 당 DFS는 N^2 걸리고, 지점은 N^2 개니까 최악 N ^ 4 걸릴 수 있다.

어떻게 최적화시켜야 할까?

2. 풀이

분명히 중복해서 계산하는 과정이 있다. 한 지점은 분명 여러번 방문될 것이며, 그 지점의 정보는 변하지 않는다.(그 지점을 방문했을 때 몇일이나 더 살 수 있는지는 변하지 않는다.)

따라서 메모이제이션과 또이나믹 프로그래밍을 써야한다.

이제 배열을 정의해보자.

DP[x][y] = 현재 내 위치가 x, y 일 때 앞으로 몇일이나 살 수 있는지 정보를 저장.

그러면 당연히 모든 이웃으로 이동이 불가능하면, 그 날만 살고 죽을테니 그런 DP[x][y] = 1 이다.

함수 func(int x, int y) = DP[x][y]를 계산해서 리턴해주는 기능을 하게 하고, 기저사례를 구분해보자.

당연히 기저사례는 위와같은 이동이 불가능한 지점이다.

아니라면, 이동가능한 지점마다 함수를 호출해주면 된다.

그런 지점으로 이동하면 하루를 더 살 수 있을테니, 그런 지점을 xx, yy 라고 하면, func(x, y) = func(xx, yy) + 1 이다.

3. 코드