백준 1570 (오세준)

백준 1570 (오세준)

문제 링크

문제 링크 : https://www.acmicpc.net/problem/1570

문제 접근

반갑습니다. 이번엔 애드 혹 문제를 해설해보려고 합니다. 왜 이 문제를 선정했냐면, 정답률이 14%밖에 되지 않았습니다. 문제를 읽어보니 해 볼 만한 생각이 들어서 풀어봤습니다. 시작 좌표와, 도착 좌표가 주어집니다. N개의 명령이 주어집니다. 명령은 U는 위로(UP), R은 오른쪽으로(right) 가는 두 방식이 있습니다. 이러한 길이 N인 명령어 조합 중, 최대한 사전순으로 앞서는 명령어를 구하는 문제입니다.

딱 봤을 때, 택시 기하학이 떠오르는 문제입니다. 택시 기하학에 대한 링크 : https://namu.wiki/w/%ED%83%9D%EC%8B%9C%20%EA%B8%B0%ED%95%98%ED%95%99

아무튼 문제를 해결해봅시다. 일단 시작점과 도착점이 얼마나 떨어져있는지를 알아야 시작이 될 듯 해보입니다. 변위를 알았으면, 적절히 조건을 분기해서 해결해봅시다. 명령의 길이 N은 고정되어 있습니다. 명령어의 조합을 잘 구해야 하는데, 거리가 꽤 멀리 떨어져 있는(맨해튼 거리가 N보다 큰 곳에 대해서는 사실 U와 R의 수가 고정되어 있기에)곳에 대해서는 순서는 딱히 중요하지 않다는 것입니다. 어차피 최소 명령어를 한 사이클 이상 돌아야 하는데,

이 말은 하나의 명령 안에는 무조건 출발점으로부터 하나의 명령어를 수행했을 때, 맨해튼 거리가 N인 곳에 도착한다는 의미입니다