(25.01.26)
문제이해
1~2칸을 한번에 움직일 때의 계단 오르는 최소 비용 구하기
문제접근
[i, i+1]에서 최소비용을 선택
우선 [i,i+1]에서 최소비용만을 선택해서 가는 걸로 코드를 짜보자.
class Solution {
public int minCostClimbingStairs(int[] cost) {
int length=cost.length;
int min_cost=0;
for(int i=0; i<length; ){
if(i>=length-2){
break;
} else if(cost[i]>cost[i+1]){//두칸을 오르는 경우
min_cost+=cost[i+1];
i+=2;
} else{
min_cost+=cost[i];
i++;
}
}
return min_cost;
}
}
case1에서 위 방식대로 진행하면 {15}가 아닌 {10,20}을 선택하는 즉 [i,i+1]에서 최솟값만 쫓다보니 최적값보다 계단을 올라야하는 횟수가 더 클 수 있다. 계단을 오르는 횟수 별 값을 계산하는 것도 좋아보인다.
계단을 오르는 횟수 별 비용 계산
계단을 한 칸 올라야 최소비용인지, 두 칸 올라야 최소비용인지는 끝까지 도달한 뒤 계산을 해봐야만 안다. 그렇다면 시작 시점에서부터 한 칸 올랐을 경우, 두 칸 올랐을 경우 등을 전부 계산한 뒤 최소비용을 갱신하면 어떨까?
우선 이를 어떻게 구현하면 좋을까? 한 칸씩 오르는 경우 계단을 cost.length만큼 오르게 되고 두 칸씩 오르는 경우 계단을 cost.length/2만큼 오르게 된다. 가장 좋은 방법은 재귀를 이용한 최솟값의 갱신으로 보인다. 그래프로도 해석할 수 있을 듯 하다.
private int recursive_search(int[] cost, int cur_index, int cur_cost){
if(cur_index>=cost.length)
return cur_cost;
if(cur_index+1<cost.length){
return cur_cost+recursive_search(cost, cur_index+1, cost[cur_index]);
}
if(cur_index+2<cost.length){
return cur_cost+recursive_search(cost, cur_index+2, cost[cur_index]);
}
return -1;
}하지만 이를 어떻게 구현해야하는지 조금 막막하다.. 백트레킹의 느낌도 나고.. 우선 전체 경우의 수를 순회시키는 것을 목표로 해보자. 문제를 조금 간소화하여 cost.length가 n인 경우 {1,1,...,1}과 {2,2,...,2}까지의 인덱스 가산 배열을 만들고 난 뒤 해당 비용을 계산해보면 좋을 듯 하다.
어떻게 코드레벨로 구현해야하는지 감이 잘 안잡히니 예시를 통해 접근해보자.
Case1) cost=10,15,20일 때 {1,1} {2}의 경우가 가능하다.
Case2) cost=1,100,1,1,1,100,1,1,100,1 일 때 {1,1,1,1,1,1,1,1,1} {1,1,1,1,1,1,1,2} ... {2,2,2,2,1}...{1,2,2,2,2} 등이 가능하다.
1만 등장하는 경우는 cost.length-1번이 반복되고 2가 가장 많이 등장하는 경우는 cost.length가 짝수인 경우 cost.length/2-1 cost.length가 홀수인 경우 cost.length/2번 등장한다. 이 계산으로 모든 경우에서 1과 2의 등장 횟수를 알 수 있고 추가적으로 고려해야하는 것은 1과 2의 배치 순서이다. 이는 인덱스 가산 값이기 때문에 순서에 따라 접근하는 cost값이 달라진다. 뭔가 굉장히 쌈뽕하게 해결할 수 있는 방법이 있을 듯 한데.. 뭘까?
우선 가산 인덱스의 합은 모두 cost.length-1이다. 2가 몇번 반복되는 경우를 for문으로 나타낸 뒤, 그에 따른 순서 배치를 섞어서 모두 계산해본다면?
public int minCostClimbingStairs(int[] cost) {
int max_two_count=cost.length-1%2==0?cost.length/2-1:cost.length/2;
int min_cost=100000;
for(int two_count=0; two_count<max_two_count; two_count++){
int one_count=cost.length-1-two_count*2;
//2 two_count개와 1 one_count개로 만들 수 있는 순서조합 계산.
int[] indexes=new int[two_count+one_count];
//2를 먼저 배치시키고 남은 자리에 1을 배치시킨다.
int cur_cost=0, prev_index=0;
for(int i=0; i<indexes.length; i++){
cur_cost+=cost[prev_index+indexes[i]];
prev_index=indexes[i];
}
if(cur_cost<min_cost){
min_cost=cur_cost;
}
}
return min_cost;
}문제는 two_count개의 2와 one_count개의 1가 배치되는 순서의 경우를 어떻게 계산하는지 잘 모르겠다.
그래프를 만들고 DFS로 최솟값 찾기
이것도 쉽지 않다.. 생성자를 어떻게 해야하는가..
public class Node{
int val;
Node left, right;
Node(int val){
this.val=val;
}
Node(int val, Node left, Node right){
this.val=val;
this.left=new Node(val);
this.right=right;
}
}
class Solution {
public int minCostClimbingStairs(int[] cost) {
Node node=new Node(cost[0]);
}
}백트레킹 응용해보기
그냥 마음이 가는대로 코드를 작성해보았다..
class Solution {
int min_cost=10000;
private void backtracking(int[] cost, List<Integer> current_indexs){
//System.out.println(current_indexs);
int cur_index=current_indexs.get(current_indexs.size()-1);
if(cur_index>=cost.length-1){
if(cur_index!=cost.length-1)
current_indexs.remove(current_indexs.size()-1);
int cost_sum=0;
for(int idx: current_indexs)
cost_sum+=cost[idx];
if(cost_sum<min_cost)
min_cost=cost_sum;
return;
}
List<Integer> new_indexes1=new ArrayList<>(current_indexs);
new_indexes1.add(cur_index+1);
List<Integer> new_indexes2=new ArrayList<>(current_indexs);
new_indexes2.add(cur_index+2);
backtracking(cost, new_indexes1);
backtracking(cost, new_indexes2);
}
public int minCostClimbingStairs(int[] cost) {
List<Integer> cur_idx1=new ArrayList<>();
cur_idx1.add(0);
List<Integer> cur_idx2=new ArrayList<>();
cur_idx2.add(1);
backtracking(cost, cur_idx1);
backtracking(cost, cur_idx2);
return min_cost;
}
}
TLE가 발생하였다. 방식은 나쁘지 않은 듯 하나 현재 current_indexes에 cost.length를 넘어서는 수까지 추가된다는 오류가 있기에 최적화를 시도하면 좋을 듯 하다.
(25.01.27)
최적화 시도
곰곰히 출력되는 current_indexes를 검토해보니 모든 경우의 수를 잘 구해내고 있었다. 그렇다면 이 시점에서 TLE가 발생한 것은.. 내 생각엔 List대신 Array같은 사소한 변화를 위하는 게 아니라 정확하게 이 문제를 깔끔히 해결할 수 있는 다른 방법이 있다고 생각한다.
문제를 다시 살펴보자. 이 문제는 난이도가 매우 쉬움이다.
index 시작 0과 1별 최소 비용 순회
혹시 시작지점에 따라 [i,i+1]범위 값만 비교하면 해결되는 문제인가? 하는 희망을 갖고 시도해보았다.
class Solution {
public int minCostClimbingStairs(int[] cost) {
int min_cost=100000, cur_cost=0;
for(int i=0; i<cost.length-1; i++){
cur_cost+=cost[i];
if(i+2<cost.length && cost[i+1]>cost[i+2]){
i++;
}
}
min_cost=cur_cost;
cur_cost=0;
for(int i=1; i<cost.length-1; i++){
cur_cost+=cost[i];
if(i+2<cost.length && cost[i+1]>cost[i+2]){
i++;
}
}
if(min_cost>cur_cost)
min_cost=cur_cost;
return min_cost;
}
}
역시나 모든 케이스를 핸들하지는 못했다. 어떻게 접근해야 할까..
계단의 끝에서부터 차례로 최단비용 배열 만들기
문제의 힌트를 참고하였다. 어떻게하면 끝에서부터 비용을 찾아낼 수 있을까?
현재 명절 피로 + 하체운동 PR 갱신으로 지친 내 머리가 작동을 잘 안한다
class Solution {
public int minCostClimbingStairs(int[] cost) {
int length=cost.length;
if(length==1)
return 0;
else if(length==2){
return cost[0]>cost[1]?cost[1]:cost[0];
} else if(length==3){
return cost[1]<cost[0]+cost[2]?cost[1]:cost[0]+cost[2];
}
int[] accumulated_cost=new int[length];
accumulated_cost[length-1]=0;
accumulated_cost[length-2]=0;
for(int i=length-3; i>=0; i--){
if(accumulated_cost[i+1]<accumulated_cost[i+2]){
accumulated_cost[i]=accumulated_cost[i+1]+cost[i];
} else {
accumulated_cost[i]=accumulated_cost[i+2]+cost[i];
}
}
return accumulated_cost[0]>accumulated_cost[1]?accumulated_cost[1]:accumulated_cost[0];
}
}
이부분에서 왜 잘못됐는지 머리가 안돌아가니 디버깅을 해보자.
디버깅을 해보니 cost가 제대로 반영이 안되서 accumulated_cost[length-1]과 accumulated_cost[length-2]의 초기화를 0이 아닌 해당 인덱스에 해당하는 cost값으로 초기화해야 할 것 같았다. 기존에 0으로 초기화 한 이유는 계단을 한칸 혹은 두칸 이동할 수 있으니 그 칸에서 바로 계단 끝으로 탈출할 수 있기에 그렇게했는데 우선 length-2이던 length-1이던 accumulated_cost 그 인덱스를 거쳤다는 것은 해당 계단을 밟아 length-2 혹은 length-1에 해당하는 cost[]를 가진다는 것이기에 바꾸었고, case 1과 case 2는 해결되었다. 제출해보자.
