20047번 - 동전 옮기기
안녕하세요. 예선에서 이 문제를 못풀어서 다시 푸는 중인데요
사실 dp? 나 재귀로 풀면 쉽게 풀린다는 블로그 글을 봤지만 제가 푼 방법대로 하니까 98퍼에서 틀렸더라구요 ..
좀 코드가 길고 더러운데 약간 그리디하게 푼 방법입니다.
먼저
3
xxo
xox 로 생각했을 때, 두 동전이 0, 2 라면
x, o 는 빼고 나머지 x를 앞에서 한번 뒤에서 한번 놓고 비교하는 방법입니다.
정방향으로 검사하면
xox
x => o, x 남음 그러면 순서 다르니까 안됨 => 역방향 탐색
x => x, o 남음 순서 맞음 => YES
만약 매칭이 안되고 남은 동전 수가 2보다 크면 무조건 NO
이런 식으로 한건데 98퍼에서 틀리더라구요 .. 제가 생각 못한 반례가 있는 걸까요 ?
아니면 아예 접근 방식 자체가 틀린 걸까요 ?
댓글을 작성하려면 로그인해야 합니다.
jokj624 3년 전
안녕하세요. 예선에서 이 문제를 못풀어서 다시 푸는 중인데요
사실 dp? 나 재귀로 풀면 쉽게 풀린다는 블로그 글을 봤지만 제가 푼 방법대로 하니까 98퍼에서 틀렸더라구요 ..
좀 코드가 길고 더러운데 약간 그리디하게 푼 방법입니다.
먼저
3
xxo
xox 로 생각했을 때, 두 동전이 0, 2 라면
x, o 는 빼고 나머지 x를 앞에서 한번 뒤에서 한번 놓고 비교하는 방법입니다.
정방향으로 검사하면
xox
x => o, x 남음 그러면 순서 다르니까 안됨 => 역방향 탐색
xox
x => x, o 남음 순서 맞음 => YES
만약 매칭이 안되고 남은 동전 수가 2보다 크면 무조건 NO
이런 식으로 한건데 98퍼에서 틀리더라구요 .. 제가 생각 못한 반례가 있는 걸까요 ?
아니면 아예 접근 방식 자체가 틀린 걸까요 ?