[C++] 백준 9465번 스티커

다이나믹 프로그래밍 문제.

엄청 오래전에 풀었던 기억이 있는데, 사실 그 땐 못 풀어서 블로그에 검색해서

이해도 못하고 그냥 코드 제출해서 맞았었다.

지금은 새로 풀었는데 초기화 안해서 한 번 틀리고 맞췄다.

 

문제풀이

어려운 문제는 아니였다.

Bottom Up 방식을 사용해서 각 칸에 도달했을 때, 어떤 경우가 최대가 될 수 있을지를 생각해보면 된다.

...	2	1	O	...	...
...	2	1	O	...

O에 갈 수 있는 경우의 수를 봐보자. 여기를 가로기준 i번째라고 한다면 각 칸에서 최대값을 기록하는 배열을

dp배열이라고 하고 각 칸의 값을 기록하는 배열을 sticker 배열이라 하고 max(A, B)를 A, B중 더 큰값을 반환한다고 하자.

• dp[1][i] = max(dp[2][i - 1], dp[2][i - 2]) + sticker[1][i]가 된다. 

어차피 dp[1][i]에서 왼쪽, 아래, 오른쪽은 고려하지 않는다. 여기에 온 이상 해당 영역들은 못 쓰는 상태이기 때문이다.

그렇다면 어디에서 올 수 있을까? 

...	2	1	O	...
...	2	1	O	...

갈 수 있는 경우의 수는 사실 많다. 저~ 멀리서 dp[1][1]에서도 파란색 O에 갈 수 있다.

그러나 우리가 원하는 것은 점수의 최대값이다. 굳이 점수가 있는데 버리고 올 이유는 없다.

그러면 어떤 경우에 모든 경우의 수를 고려해줄 수 있을까?

바로 위에서 설명한 dp[2][i - 1](1), dp[2][i - 2] (2)만 고려해주면 된다.

• 파란색 1번이 대각선을 타고오는 경우의 수를 모두 고려해준다.
• 파란색 2번이 파란색 O와 같은 라인에 있고 파란색 2번에서 한칸 건너뛰는 경우를 고려해준다.

이해가 잘 안된다면 예시 입력으로 주어진 테스트 케이스들로 그림을 그려보면 된다.

보라색 O도 위 아래를 뒤집어서 고려해주면 된다.

 

코드를 살펴보자. 굉장히 짧다.

 

사용한 STL과 변수

테스트 케이스의 개수와 가로의 길이의 변수를 만든다.

그리고 각 스티커의 값과 각 칸에 도달했을 때의 최대값을 담을 배열을 만들어준다.

사이즈가 3인 이유는 1, 2로 사용하기 위해서이다.

 

메인함수 - 1

처음에 테스트 케이스의 개수를 입력받는다.

각 테스트 케이스마다 너비를 입력받고 스티커의 값들을 입력받는다.

후에 dp배열의 최초값을 초기화하는데, 내 점화식 같은 경우

- 2가 최대값이므로 가로길이 2까지는 수동으로 초기화시켜준다.

 

그리고 result 값을 최초로 초기화해야한다.

초기화 해주지 않아서 한 번 틀렸다.

 

메인함수 - 2

그리고 반복문을 돌면서 각 칸에서의 최대값을 갱신한 후, 모든 칸에서의 최대값을 출력한다.

이를 테스트 케이스가 끝날 때 까지 반복한다.

 

예전에 풀었었는데, 기억은 확실히 안난다.

아마 저 땐 아무것도 모르고 그냥 풀었던 것 같다.

이제는 혼자 이런문제정도는 쉽게 풀 수있는것 같다.

근데 DP는 정말 실버1, 실버2가 하늘과 땅의 차이인 것 같다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인 가능하다.