3238번 - LINIJE
원 문제 기준으로 5s 의 시간을 주던 문제였고, 정해 기준으로 1s 내에 풀릴지 의문인 것 같습니다.
(https://hsin.hr/2003/)
제가 부족하여 그런 걸 수도 있으니 확인해 주시고 조치 필요하면 부탁드립니다.
이거 혹시
3 3
2 1 2
2 1 3
2 2 3
이 입력이 들어왔을때 답이 뭐여야하나요?
제가 지문을 이해한 바로는
3
1 2 3
이 맞다고 생각하는데
정해 코드는
2
1 2 2
를 뱉네요...
노선을 정점이라 하고 서로 같은 색이면 안되는 정점끼리 간선으로 이어준다 생각하면 k-coloring라는 NP-완전문제로 완벽하게 변환할 수 있어서 못푸는 문제 같아보이는데 지문 이해를 제대로 했는지 모르겠네요
그런줄은 몰랐네요.. 그럼 이 문제는 못푸는 문제인건가요?
그새 푸신 분이 생긴거 보면 제가 잘못 이해한게 맞았나보네요...
푸신 분께 여쭤보는 것이 빠를 것 같습니다
철도가 트리 형태로 깔려 있고 각 트램은 그 트리의 어떤 단순 경로에 속하는 철로들을 사용한다고 이해하고 풀었습니다.
해결 되는 문제군요 ㅎㅎ 천천히 다시 생각해 봐야겠어요
트리에서 내려오면서 하는 방식이 있었네요. 다른 문제 풀다 급! 생각나서 풀어보니 됩니다 ㅎㅎ 감사해요~
댓글을 작성하려면 로그인해야 합니다.
my016658 2년 전
원 문제 기준으로 5s 의 시간을 주던 문제였고, 정해 기준으로 1s 내에 풀릴지 의문인 것 같습니다.
(https://hsin.hr/2003/)
제가 부족하여 그런 걸 수도 있으니 확인해 주시고 조치 필요하면 부탁드립니다.