병든 나이트
-
모각코 PS스터디 / 백준 1783 병든 나이트PS 2022. 5. 21. 16:44
모각코 PS스터디 왜인지 모르겠는데 PS는 하고 나서 포스팅 하는 걸 자꾸 까먹는다. 이번주 스터디 한 세 문제를 차례로 포스팅해보려고 한다. 문제와 풀이 문제 링크 : 백준 1783번 - 병든 나이트 👇펼쳐서 코드와 해설 읽기 이 문제도 역시 그리디(greedy) 카테고리의 문제다. 얼핏 보면 탐색 같지만, 표본 수(2,000,000,000)를 보면 탐색으로 했을 때 무조건 타임아웃이 날 거란 걸 생각해볼 수 있다. 충족할 조건은 2가지다. 이동횟수를 최대화할 것. 이동방식을 충족할 것. (밟은 발판 갯수가 5개 이상 시에만) 나이트의 이동경로는 다음 네가지다 2U 1R 1U 2R 1D 2R 2D 1R 네 가지 이동을 완수하는 케이스를 먼저 생각해보기로 했다. 네 가지 이동을 완수하고 나서도 시작점에 ..