알고리즘

문제 링크 문제 설명 신규 게임 ‘카카오 미로 탈출’이 출시되어, 라이언이 베타테스터로 참가했습니다. 위 예시 그림은 카카오 미로 탈출의 초기 상태를 나타냅니다. 1번부터 3번까지 번호가 붙어있는 3개의 방이 있고, 방과 방 사이를 연결하는 길에는 이동하는데 걸리는 시간이 표시되어 있습니다. 길은 화살표가 가리키는 방향으로만 이동할 수 있습니다. 미로에...

문제링크 문제설명 어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 a kg과 은 b kg이 전달되어야 합니다. 각 도시에는 번호가 매겨져 있는데, i번 도시에는 금 g[i] kg, 은 s[i] kg, 그리고 트럭 한 대가 있습니다. i번 도시의 트럭은 오직 새 ...

문제 링크 문제 풀이 냅색 문제와 유사하다는 생각이 드는 문제였다. 비슷한 방식으로 풀이를 진행했으나 끝에 생각하지 못한 오류가 있어 다른 글들을 참고했다. 주어지는 메모리가 10,000,00이기 때문에 메모리를 기준으로 DP배열을 만들면 시간초과가 날 것이라고 생각했다. 따라서 비용을 기준으로 DP배열을 만들어줬다. 이에 따른 점화식은, 이다...