백준 17391. 무한 부스터

tose33 2022. 9. 3. 15:08

17391번: 무한부스터

카트라이더를 처음 시작하는 카린이 정범이는 어려운 조작법에 실망감이 커져가고 있다. 드리프트, 순간 부스터, 커팅, 톡톡이 등등 어려운 테크닉에 질린 정범이는 그나마 쉬운 ‘숭고한 무한

www.acmicpc.net

dp 문제.

d[i][j] : [i][j]에 도달하는데 먹게되는 부스터의 최소 갯수

좌표들을 돌면서 현재 좌표의 부스터 갯수가 B개라고 하면, 현 좌표에서 오른쪽으로 1칸~B칸, 아래로 1칸~B칸 갈수 있다.

d[i][j]가 해당 좌표에 도달하는데 먹게되는 부스터의 최소 갯수이므로 도달할수 있는 좌표가 d[a][b]라고 하면 d[a][b] = min(d[a][b], d[i][j]+1) 이 된다.

물론 최초에 d는 INF 값으로 초기화 해야 한다.