티스토리 뷰
한 2주 동안 고민해서 풀었는데, 사실 간단한 방법이라서 허무했다.
영선이와 효빈이가 각자 뭘 고를지를 정할 필요 없이, 마지막에 골라진 두 수만 알고 있으면 된다.
D[i][j]를 i번째 수와 j번째 수가 마지막 수일 때 최소 난이도라고 정한다.
그러면 경우는 3가지가 있다.
영선이가 쭉 골라오다가 효빈이가 지금 처음 고르는 것이라면 D[i][i−1]는 현재까지의 난이도 총합이 된다.
그리고 i−1번째 수와 j번째 수가 마지막인 경우, D[i−1][j]에서
i−1번째 수에서 i번째 수로 넘어온다면 D[i][j]를 갱신할 수 있고,
j번째 수에서 i번째 수로 넘어온다면 D[i][i−1]를 갱신할 수 있다.
'문제' 카테고리의 다른 글
BOJ 1819 불끄기 (0) | 2018.10.25 |
---|---|
BOJ 12945 재미있는 박스 정리 (0) | 2018.09.26 |
BOJ 2171 직사각형의 개수 (0) | 2018.08.12 |
BOJ 1019 책 페이지 (0) | 2018.08.08 |
BOJ 8217 유성 (0) | 2018.08.07 |