본문 바로가기

Algorithm283

[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]13308번: 주유소 https://www.acmicpc.net/problem/13308 jason님 풀이를 바탕으로 해결하였습니다. (https://jason9319.tistory.com/249) 거리와 비용 최소화라는 2가지 정보로 판단해야 합니다. 그렇기 때문에 단순히 dist[N] 1차원 배열로는 모든 정보를 담을 수 없습니다. 그래서 dist[N]과 같은 역할을 하는 2차원 dp테이블을 사용합니다. dp[node][minOilCost] 정의 : 1번 노드부터 순회하여 node까지 왔고, 지금까지 방문한 주유소의 기름 가격 중 최소 기름 가격 그리고 이 dp table에 node를 방문하며 쌓인 totalCost 값을 집어넣는 것입니다. dp[node][minOilCost] = totalCost 이런식으로 다익스트라를.. 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]11723번: 집합 https://www.acmicpc.net/problem/11723 비트 연산자를 사용해서 해결하는 문제입니다. 모든 연산에 공통으로 사용되는 개념은 특정 숫자를 확인한다는 것은 특정 숫자를 특정 위치 비트까지 민다는 것을 의미합니다. num은 비트 연산에서 (1 2020. 8. 24.

티스토리툴바