2647번 - 검은점과 하얀점 연결
그리디하게 1와 0을 가까운 것끼리 최대한 연결하면 될 것 같아, 유니온 파인드를 이용했습니다
ex)
1100 이라면
첫번째와 두번째 1은 그냥 패스시키고,
세번째 0을 바로 앞수와 연결시켜서, pair (find(3-1), 3) == (2,3)을 답으로 저장하고, merge(find(3-1)-1, find(3-1))을 합니다.
네번째 0을 바로 앞수와 연결시켜서, pair (find(4-1), 4)==(1,4)을 답으로 저장합니다.
이렇게 했는데, 18%에서 틀립니다.
알고리즘이 틀린 걸까요? ㅠㅠㅠㅠ
도저히 감이 안오네요...
댓글을 작성하려면 로그인해야 합니다.
QuqqU 4년 전
그리디하게 1와 0을 가까운 것끼리 최대한 연결하면 될 것 같아, 유니온 파인드를 이용했습니다
ex)
1100 이라면
첫번째와 두번째 1은 그냥 패스시키고,
세번째 0을 바로 앞수와 연결시켜서, pair (find(3-1), 3) == (2,3)을 답으로 저장하고, merge(find(3-1)-1, find(3-1))을 합니다.
네번째 0을 바로 앞수와 연결시켜서, pair (find(4-1), 4)==(1,4)을 답으로 저장합니다.
이렇게 했는데, 18%에서 틀립니다.
알고리즘이 틀린 걸까요? ㅠㅠㅠㅠ
도저히 감이 안오네요...