백준 알고리즘44 [BOJ]1102번: 발전소 https://www.acmicpc.net/problem/1102 bitmasking + dp 문제입니다. sungwoo님의 블로그 내용을 참고하여 해결하였습니다. (https://sungwoo91.tistory.com/12) dp테이블은 다음과 같습니다. dp[N][state]: N: 현재 N개의 발전소가 켜져있고, state: N개 중에 어떤 발전소가 켜져있는 상태를 나타냅니다. 그리고 dp table에 위와 같은 상태를 만드는데 드는 최소 비용만을 저장해놓습니다. dp[N][state] = minCost 그래서 P개를 모두 켰을 때 최소의 비용을 구하면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1102.cc 2020. 8. 28. [BOJ]1562번: 계단 수 https://www.acmicpc.net/problem/1562 jason님 풀이를 참고해서 해결하였습니다. (https://jason9319.tistory.com/135) dp + bit masking을 통해 해결할 수 있습니다. 계단 수를 완성하는데 0~9 까지 모든 수를 사용해야 합니다. 이는 비트로 표시하여 (1 2020. 8. 27. [BOJ]2589번: 보물섬 https://www.acmicpc.net/problem/2589 문제 해결의 핵심은 그래프 크기가 작다는 것입니다. W, H제한이 50이므로 모든 칸에 대해 새롭게 BFS를 돌아도 시간복잡도는 O(50^4) 이므로 시간초과가 나지 않습니다. W*H칸에 존재하는 모든 육지에 대해 BFS를 돌아서 자신이 가장 멀리 도달한 지점을 저장해놓습니다. 이렇게 멀리 도달한 지점들의 MAX값을 구하면 그게 정답입니다. https://github.com/cottory/algorithm/blob/master/BOJ/BOJ2589.cc 2020. 8. 22. [BOJ]5427번: 불 https://www.acmicpc.net/problem/5427 매 초 마다 불이 붙어있는 모든 칸이 다른 칸으로 전파 될 수 있습니다. 그리고 상근이는 불이 옮겨 붙을 칸으로 이동할 수 없습니다. 그러므로 맨 처음 큐에 넣어줄 때 불이 있는 칸이 상근이가 있는 칸보다 먼저 넣어주면 됩니다. 큐 사이즈만큼만 루프를 돌면서 매 초마다 불이 이동하는 칸과 상근이가 이동하는 칸을 확장해 나가면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ5427.java 2020. 8. 22. 이전 1 2 3 4 5 6 7 8 ··· 11 다음
