나를 잃지 말자

문제:www.acmicpc.net/problem/1912

비고:

-Dynamic programming

-예제2에서 문제 포인트를 알아차려야했는데 놓쳤다.

2 1 -4 3 4 -4 6 5 -5 1 에서 6 5->11이 답이라고 착각하였다. 답은 3 4 -4 6 5로 14다.

-여기서부터 문제를 파악하고 해결해 나가자.

-각 index마다 left max값과 right max값 그리고 index에서의 값을 다 더하고 취합하고 취합한 것에서 max를 구하면 된다.

-각 점마다 left max를 dictionary로 박자. 이 때, index가 작은 순부터 left max를 구하는 것에서 dynamic programming

-0에서는 left max가 0, 1에서는 left max가 0에서의 leftmax + 0에서의 값, 이 때 이 더한 값이 음수면 1에서의 leftmax는 0, 양수면 그 값을 1에서의 left max로 택한다.

-이러면 n번의 계산으로 모든 점에서의 left max를 구한다.

-마찬가지로 n번의 계산으로 모든 점에서의 right max를 구한다.

-문제파악에서 차질이 생겼다. 다음에는 반드시 예제의 정답을 믿자. 예제가 틀렸다고 생각하다니...ㅉㅉ

-게다가 사람들이 많이 푼 문제에 오류가 있다고 생각하면 되겠냐

-난이도중

내소스코드:

boj.kr/12104c7b668241f7b7ef8ee4d6ab8541

문제:https://www.acmicpc.net/problem/14852

비고:

-Dynamic programming 활용

-점화식을 짤 때, 1개만 할지 보조를 둬야할 지 감이 옴

-이 문제는 다음과 같음

  -f(0)=1, f(1)=2, g(1) = 1

  -g(n) = g(n-1) + f(n-1)

  -f(n) = f(n-2) + g(n-1) + f(n-1) + g(n)

-매 결과를 저장할 배열같은게 필요하지 않음, 마지막 가짓수만 새면 됨

-결과를 나머지로 뱉어야되는 경우, 개별 계산에서 미리해서 숫자 절댓값 줄여서 계산하기 필요(이 짓을 안했더니 "시간초과" 받음)

내소스코드:

boj.kr/782710fea2044c59b94b89039aa4c440

문제:https://www.acmicpc.net/problem/2133

비고:

-Dynamic programming 활용

-bottom-up이어서 왼쪽에서부터 오른쪽으로 타일이 하나씩 늘어나는 상황 생각해서

점화식을 D[n] = 3*D[n-2] + 2*D[n-4]로 생각했다가 고생했다.

여기서 3은

--

||

||케이스와

--

--

--케이스

||

||

--케이스 해서 총 3가지

2는

----

|--|

|--|와

|--|

|--|

----

이 때 n=6일 때 고려하지 못한 케이스가

------

|----|

|----|와

|----|

|----|

------이다.

따라서, 경우를 나눌 때, 우측 상단에 --로 시작해서

--

--

--로 끝나는 경우와

--

 |

 |

그리고

 |

--

--인 경우, 근데 마지막 2가지는 상하대칭성을 띄니까 1개의 함수로 세자

따라서, 구하고자하는 ans(n)과 보조함수 aux(n)을 정의

ans(n) = ans(n-2) + aux(n-1)

aux(n) = ans(n-1) + aux(n-1)

ans(0) = 1, ans(1) = 0

aux(0) = 0, aux(1) = 1로 두고 풀면 된다.

-매 결과를 저장할 배열같은게 필요하지 않음, 마지막 가짓수만 새면 됨

내소스코드:

boj.kr/7be8dbc0db4445888d24df8c7db663e8

문제:https://www.acmicpc.net/problem/11727

비고:

-Dynamic programming 활용

-bottom-up이어서 왼쪽에서부터 오른쪽으로 타일이 하나씩 늘어나는 상황 생각해서

점화식을 D[n] = D[n-1] + (D[n-2] * 3) 에서  *3로 생각하면 안됨

(D[n-2]에서 2x1을 2개, 1x2을 2개, 2x2을 1개 사용하는 방식 총 3가지니까 *3하려고한다면, 3개 중 첫번째는 D[n-1]에서 count해서 중복발생)

따라서 D[n] = D[n-1] + D[n-2]*2

-매 결과를 저장할 배열같은게 필요하지 않음, 마지막 가짓수만 새면 됨

내소스코드:

boj.kr/d99f1a90f14341a090c4ba58bd460c33

문제:https://www.acmicpc.net/problem/11726

비고:

-Dynamic programming 활용

-bottom-up이어서 왼쪽에서부터 오른쪽으로 타일이 하나씩 늘어나는 상황 생각해서

점화식을 D[n] = D[n-1] + (D[n-2] * 2), *2로 생각하면 안됨

(D[n-2]에서 2x1을 2개, 1x2을 2개 사용하는 방식 총 2가지니까 *2하려고한다면, 2개 중 전자는 D[n-1]에서 count해서 중복발생)

따라서 D[n] = D[n-1] + D[n-2]

-매 결과를 저장할 배열같은게 필요하지 않음, 마지막 가짓수만 새면 됨

내소스코드:

boj.kr/a173cca197ca42eb88e87bd88c47a6ba