본문 바로가기

분류 전체보기361

[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.
[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.

티스토리툴바