11058 크리보드

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

11058번: 크리보드

 

어렵다

혹시 DP인가 싶어서 2차원 DP테이블을 시도해봤는데 잘 안되길래 끙끙대다 태그 까봤더니 DP였음

근데 DP인거 알고도 DP테이블가지고 끙끙댐

근데 쉽게 생각해볼까 해서 1차원 DP테이블로 해봤더니 대충 되는거 같길래 1차원으로 DP짬

근데 틀림

그래서 걍 테케 참조해봤더니

N = 8 일 때 해가 12이고

N = 9 일 때 해가 16이길래 띠용 해서

대충 수정해서 다시 냈더니 통과

 

다른사람 풀이 봤더니 i-3 기준으로 1씩 줄어들때마다 배수가 늘어남

그 값들중 최댓값을 현재 DP[i]에다 집어 넣는 방식으로 하던데

근데 모든 사람들 풀이가 비슷하니 어디서 배낀거 같아서 난 걍 내껄로 코드 픽스하기로 함

그래봤자 로직 자체는 다 비슷함

 

https://github.com/KimximyaFan/Random-Defense/blob/main/C0007.java