7981번 - 장비를 정지합니다
4 3 100 2 2 3 4 14 1 4 1 8 1 2 1 2 1 3
입력이 위와 같다면 답은 16입니다.
1번을 약한 충격으로 (총 비용: 3, 작동중: 2, 3)
2번을 약한 충격으로 (총 비용: 3+4, 작동중: 3, 4)
4번을 강한 충격으로 (총 비용: 7+2, 작동중: 3)
3번을 약한 충격으로 (총 비용: 9+1, 작동중: 2)
2번을 약한 충격으로 (총 비용: 10+4, 작동중: 4)
4번을 강한 충격으로 (총 비용: 14+2, 작동중: x)
dfs로 했을 때 1, 2, 4, 3, 순으로 방문하면 3번의 비용이 8로 계산됩니다.
하지만 위에서 나와있는 것처럼 3->4->2로 하면 비용이 7입니다.
풀이의 힌트는..
문제의 태그 보시면 생각치도 못한 태그가 하나 있습니다.
태그를 보시고도 떠오르지 않으시다면 해당 태그와
https://www.acmicpc.net/proble...
이 문제를 적절히 조합해보시면 도움이 될 것 같습니다.
댓글을 작성하려면 로그인해야 합니다.
exqt 3년 전 3
입력이 위와 같다면 답은 16입니다.
1번을 약한 충격으로 (총 비용: 3, 작동중: 2, 3)
2번을 약한 충격으로 (총 비용: 3+4, 작동중: 3, 4)
4번을 강한 충격으로 (총 비용: 7+2, 작동중: 3)
3번을 약한 충격으로 (총 비용: 9+1, 작동중: 2)
2번을 약한 충격으로 (총 비용: 10+4, 작동중: 4)
4번을 강한 충격으로 (총 비용: 14+2, 작동중: x)
dfs로 했을 때 1, 2, 4, 3, 순으로 방문하면 3번의 비용이 8로 계산됩니다.
하지만 위에서 나와있는 것처럼 3->4->2로 하면 비용이 7입니다.
풀이의 힌트는..
문제의 태그 보시면 생각치도 못한 태그가 하나 있습니다.
태그를 보시고도 떠오르지 않으시다면 해당 태그와
https://www.acmicpc.net/proble...
이 문제를 적절히 조합해보시면 도움이 될 것 같습니다.