1202번: 보석 도둑 아이디어 생각해내는게 너무 어려웠다. 처음에는 보석 이 들어가길래 습관적 DP로 생각했는데, 각 가방의 크기가 너무 커서 배열로 담을 순 없다는 것을 깨달았다. 그래서 ‘가방의 사이즈를 배열의 값으로 담아 K개 저장한뒤 오름차순으로 정렬해야겠다’까지는 쉽게 생각이 났다. 그 뒤로 한 시간 이상 고민했고, 풀이방법만 봐야겠다 싶어 확인해봤는데 아이디어는 간단했다. 우선순위 큐를 두개 준비한다. 하나는 무게를 오름차순으로 정렬하고 하나는 가치를 기준으로 정렬할 것이다. 이를 각각 pqByWeight와 pqByValue라고 하겠다. 입력받은 모든 보석들을 pqByWeight에 넣는다. 가방을 입력받고 가방의 최대무게를 오름차순으로 정렬한다. 각 가방의 최대 무게마다 해당 무게보다 낮은 ..
전체 글
12865번: 평범한 배낭 대표적인 0 - 1 배낭 문제이다. 물건 N개와 배낭의 크기인 K가 주어지고 2번째 줄부터 물건의 가치와 무게가 주어진다. 이때 최대 가치를 구하는 문제다. 4 7 6 13 4 8 3 6 5 12 문제와 같이 예제가 주어졌을 경우 최대 담을 수 있는 물건은 4개 배낭의 최대 사이즈는 7이된다. 이에 맞는 배열을 준비하면 dp = new int[5][8]이 된다. 물건과 사이즈는 0이 될 수 없으므로 +1씩 해줬다. dp[0] = [0,0,0,0,0,0,0,0] dp[1] = [0,0,0,0,0,0,0,0] dp[2] = [0,0,0,0,0,0,0,0] dp[3] = [0,0,0,0,0,0,0,0] dp[4] = [0,0,0,0,0,0,0,0] 위와 같이 dp 배열이 초기화되어 ..
1106번: 호텔 0 - 1 배낭 문제로 생각하고 접근해야 하는 문제이다. 다만 배낭 문제의 경우 배낭 무게가 정해져 있어 무게를 초과한다면 넣을 수 없지만 이 문제의 경우 최소 C명 이상의 고객을 얻을 수 있는 최소 비용이기 때문에 C명을 넘더라도 최소 비용이라면 해당 값을 반환해야 한다. 풀이 과정 dp의 경우 C + 1명이 아닌 C + 101명으로 초기화 해주었는데 이는 하나의 도시에서 홍보를 통해 얻을 수 있는 고객이 최대 100명이기 때문이다. 앞서 말했듯 최소 C명이상의 고객을 얻을 수 있는 최소 비용이기 때문에 넘을 수 있는 최대 고객 수인 100명과 1번 인덱스부터 사용하기 위해 1명을 추가해줬다. 최소 비용을 구하는 문제이기 때문에 dp를 적당한 무한값으로 초기화해주고 0명을 얻기 위해서..
30869번- 빨리 기다리기 백준 아레나 신청해놓고 까먹고 있다가 부랴부랴 기억해서 참가했었다. 한 시간 반정도 남았을 때 도전했는데 처음 봤을 때는 쉽게 생각하고 BFS로 접근했었다. 제출하니까 시간 초과 뜨길래 다익스트라로 방향을 바꿨으나 시간이 없어서 못풀었었다. 그리고 다 풀고 나서 또 조건 제대로 안 읽어서 불가능할 경우 -1을 출력한다는 것을 못봤다. 그리고 나서는 ‘아 혹시 시간 합이 long이라서 그런가?’ 하고 엉뚱한 것만 손보고 있었다. 이것 때문에 한 15분 정도 더 해멨다.. 결국 접근법 자체는 다익스트라가 맞았다. 대신 고려해야할 점이 빨리 기다리기인데 빨리 기다리기를 사용하면 배차간격을 무시하고 바로 탈 수 있다는 점이다. 예시로 바로본다면 ① -> ②로 가는 소요시간은 2시간이..