학습(알고리즘)

1.오른쪽, 아래, 우측아래 3가지 방향으로 이동할 수 있을 경우 특정 위치에 도달하는 경우의 수를 구하는 방법은 일반적인 dp를 구하는 방식과 유사하지만 세가지 경로를 비교해서 넣어줘야 한다는 부분이 다르다. a,b의 좌표라고 가정하면 a-1,b a,b-1 a-1,b-1 3가지의 경로의 합을 dp에 배정해주면 된다.

2.이차원적인 배열 또는 여러줄의 값을 받아올 때는 값의 비교를 잘 해야 하는데]
아래의 코드를 자세히 보면 input[i+a-1]의 값이 NaN으로 나오는 것을 볼 수 있다.
코드에 NaN이 나온다는 사실이 이해가 안되서 단계적으로 콘솔을 찍어보니
이차배열 자체를 Number로 바꿔준 것이 아니라 여기 내부에서만 input[i]의 [0], [1] 번째 값만 구조분해 할당으로 사용했기 때문에 input[i]등 어떠한 input의 값도 받아올 수 없는 것이었다. 왜냐하면 input[i]는 문자열이기 때문이다..

for(let i = num ; i > 0 ; i--){
    let [a,b] = input[i].split(' ').map(Number)

    if(i+a-1 < num){
            // console.log(i,a, dp[i+a-1], b)
        // console.log(dp[i+1] , dp[i+a-1] + b, input[i+a-1] + b)
        dp[i] = Math.max(dp[i+1] , dp[i+a-1] + b, Number(input[i+a-1].split(' ')[1]) + b)
    }

3.작업시간에 따라 수주할 수 있는 일을 확인하려면 역으로 추적해야 하는데

  1.만약 이 일이 종료기간 전에 달성할 수 있는지 체크한 후 가능해야만 진행하므로 if체크
  2.해당하는 뒤에서 첫번째 날짜 X에 벌어들인 수익을 dp에 저장
  3.이전 날짜를 쭉 체크하며 날짜에서 종료 전에 끝낼 수 있는 경우  현재 시작한 일을 끝낸 날의 다음날의 수익과 
  현재 시작할 일의 수익을 더하고 그 값을 이전에 체크한 날짜 (여기선 역추적이므로 5일이라면 6일, 3일이라면 4일 등)의
  수익과 Math.max를 통해 비교 후 더 큰 수입을 채택하는 방식으로 dp[1]인 현재 날짜에서 최종적으로 벌어들일 수 있는 
  최대 수익값을 알아볼 수 있다.

 

4.dp에서 if문을 사용할 경우 if에 해당하지 않는 값들도 실시간(?)으로 값이 반영이 되야 그 다음 또는 이전 값으로 진행할 때 현재 최대값을 제대로 받아올 수 있다.
그렇기 때문에 아래의 경우 if문 아래에 있는 else문으로 초기화를 해줘야만 했다.

    if(i+a-1 <= num){ Number(input[i+a-1].split(' ')[1]) + b)
        dp[i] = Math.max(dp[i+a] + b , dp[i+1])
    }
    else{
        dp[i] = dp[i+1] //이부분이 없다면 if문에서 벗어난 중간 dp값은 default값이 되어 착오를 일으킬 수 있다. 현재 최대/최소값이 제대로 반영돼야 한다.
    }

 

5.최대값을 그냥 구하는 것과는 다르게 원하는 조건의 무게 또는 수치를 정확히 맞출 수 있는 값 중 최소 또는 최대값을 구하는 경우 일반적인 방법으로 dp를 적용시키면 문제가 발생할 가능성이 높다. 왜냐하면 일반적인 dp는 나누어 떨어지지 않는 값들도 전부 적용시키기 때문인데 이를 방지하기 위해서 아래와 같은 코드를 사용해야 한다.

if(j >= b){
	if(!dp[j-b]&& b%j){
		continue
	}
	dp[j] = Math.max(dp[j-b] + a , dp[j])
}

 

6.문제를 읽을 때 범위를 자세히 읽어야 하는데 0 <= n <= 50인 경우 0도 고려를 해야한다.
상식적으로 dp문제에서 0을 물어볼줄 모르고 dp[1], dp[2]만 이용해(dp[i] -1,-2만 사용하기 때문에) 문제를 풀었는데 자꾸 오답이 나와 곰곰히 생각해보니 dp[0]값을 배정해주지 않아서 input이 0인 경우 오답이 나온 것이다.  입력값이 어떤 범위인지 다시 한번 생각하자.

7.동전 값을 넣어서 비교할 경우 Math.min을 작성해야 한다. 하지만 그럴 경우 초기값 0이 제대로 들어가지 않을 수 있기 때문에 잔돈이 1원일 경우는 따로 작성해줘야 하단에서 Math.min을 사용할 수 있다.