- Minimum Cost For Tickets
983. Minimum Cost For Tickets Acceptance 57.7%
NOTE
블로그라기 보다는 생각나는 생각나는 대로 두서없이 적는 낙서장이라고 보면 될것 같다.
2019년 3월 22일 13:34~15:46
문제
- DP 문제는 기본이 medium 문제네
- 두 개의 배열이 주어질때, days는 1, 365일까지 여행하는 날짜를 주고, costs는 3개의 요소로 각각 1일 패스, 7일 패스, 30일 패스의 가격을 주네. (예: days = [1,4,6,7,8,20], costs=[2,7,15])
- 이 때, 전체 여행 경비의 최소 경비는 11 (첫째날과 마지막날 2일을 1일 패스, 나머지는 7일패스)
- 제약 사항: 1 <= days.length <= 365 1 <= days[i] <= 365 days is in strictly increasing order. costs.length == 3 1 <= costs[i] <= 1000
- 무식하게 모든 경우의 수를 구해서 최소의 값을 구한다. 이 경우, days의 길이를 $n$이라 하면 $n^3$인가?? 3승은 costs의 길이… 왜냐하면 각 day의 값마다 어떠한 cost든 적용할 수 있기 때문에 중복순열인듯?
- 좀 쉽게 접근하기위해 루트가 3개인 트리로 생각했다. 각 노드는 costs 배열의 길이만큼 자식 노드를 가지게 된다.
- 아래와 같이 해보자.
이래서는 days가 길어질 수록 기하급수적으로 계산량이 많아지므로 못써먹는다. 실제로도 타임 아웃이 났는데, 아래 케이스를 통과하지 못했다. 내 랩탑에서도 3.8 초가 걸렸다.
//62개
int[] days = new int[]{1,2,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,20,21,24,25,27,28,29,30,31,34,37,38,39,41,43,44,45,47,48,49,54,57,60,62,63,66,69,70,72,74,76,78,80,81,82,83,84,85,88,89,91,93,94,97,99};
int[] costs = new int[]{9,38,134};
2019년 3월 22일 14:27-15:00
어제는 무식하게 하니깐 좀 많이 느려서 트리에서 가지치기를 해보려한다. 내 생각의 시작점이 트리니깐, BFS를 응용해보자. 1) 최 외곽 루프는 days 순회 2) 큐는 두 개, 한 개는 패스 누적 여행 가능 일수, 남은 하나는 누적 비용 3) 내부 루프 하나를 만들어서 큐 하나의 사이즈 만큼 돌린다. 4) “현재 날짜와 > 누적 여행 가능 일수”라면, 현재 날짜를 여행할 수 있을 만큼 1일 패스, 7일 패스, 30일 패스 세 가지 경우의 비용을 늘리도록 해서 큐에 넣는다.
- 이로 인해서 생기는 노드는 위 경우가 발생한 횟수*3이 될 것이다. 5) 내부 루프를 돌면서 최소 누적 비용을 기억한다. 6) 다 돌면 최소 누적 비용을 리턴
재활용할 수 있는 코드가 하나도 없네;; $O$ 노테이션으로 이걸 어떻게 계산해야할지 모르겠다. 일단 days의 길이 $N$이라하고, 큐 안에 원소가 많을 수록 손해긴한데… 가장 많으려면? $N=365$인 경우가 1일 패스로 인해서 발생하는 노드가 가장 많아지겠지?
아… 거의 계산량이 안 줄어드네;;
흠… 역시 메모이제이션인데 익숙하지가 않아서….
- 365일을 배열로 선언하고 각각에 대해서 비용을 재귀적으로 레이지하게 초기화한다….
- 아 days에 속한 애들이 아니면 직전값을 쓰면 1.에 선언한 배열의 마지막 값은 내가 원하는 값이 되겠네
- days를 set으로 만들면 되겠다.
2019년 3월 25일 16:00~16:30
- 한 번 생각이 나니깐 금방하네;;
- 생각하기까지의 시간을 단축해야겠다. 여러 문제를 풀어봐야
Leave a comment