jokj624   3년 전

안녕하세요. 예선에서 이 문제를 못풀어서 다시 푸는 중인데요

사실 dp? 나 재귀로 풀면 쉽게 풀린다는 블로그 글을 봤지만 제가 푼 방법대로 하니까 98퍼에서 틀렸더라구요 .. 

좀 코드가 길고 더러운데 약간 그리디하게 푼 방법입니다.

먼저 

3

xxo

xox 로 생각했을 때, 두 동전이 0, 2 라면

x, o 는 빼고 나머지 x를 앞에서 한번 뒤에서 한번 놓고 비교하는 방법입니다.

정방향으로 검사하면

xox

x             => o, x 남음 그러면 순서 다르니까 안됨 => 역방향 탐색 

xox

    x         => x, o 남음 순서 맞음 => YES 

만약 매칭이 안되고 남은 동전 수가 2보다 크면 무조건 NO

이런 식으로 한건데 98퍼에서 틀리더라구요 .. 제가 생각 못한 반례가 있는 걸까요 ?

아니면 아예 접근 방식 자체가 틀린 걸까요 ?

댓글을 작성하려면 로그인해야 합니다.