[BOJ] 6988번: 타일 밟기

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


우선 $pos[i]$에 $i$가 적힌 타일이 몇 번째 타일인지를 저장해둡니다.(미리 -1로 초기화해두어 어디에도 적혀있지 않은 값은 -1로 둠) $D[i][j]$를 $A[j]$를 초항으로, $A[i]$를 두번째 항으로 하는 내림 등차수열의 합이라 할 때 세번째 항은 $2 \times A[i] - A[j]$ 이므로 $pos[2 \times A[i] - A[j]]$ 가 -1이라면 $D[i][j]$를 $A[i]+A[j]$로 두고, -1이 아닌 $k$라는 값이면 $D[i][j]$를 $D[k][i]+A[j]$로 두면 됩니다.


되게 오랜만에 풀이를 올리네요.


https://github.com/blisstoner/BOJ/blob/master/6988.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 12895번: 화려한 마을  (0) 2019.01.14
[BOJ] 1477번: 휴게소 세우기  (0) 2019.01.14
[BOJ] 2461번: 대표 선수  (0) 2019.01.13
[BOJ] 6988번: 타일 밟기  (0) 2019.01.10
[BOJ] 1208번: 부분집합의 합 2  (0) 2018.12.18
[BOJ] 16678번: 모독  (0) 2018.12.17
[BOJ] 13711번: LCS 4  (0) 2018.11.26
  Comments
댓글 쓰기