오늘 배운 내용
숫자 변환하기
이번 주 첫 TIL은 프로젝트가 아직 정리가 안된거 같아서 코드카타때 푼 문제로 작성해야 될 것 같다.
이번 문제는 자연수 x를 세 가지 연산을 사용해서 y로 만들때 최소한으로 연산을 사용한 경우의 수의 연산 횟수를 구하는 문제 였다.
문제를 보자마자 딱 DP가 떠올랐고, 세가지 연산을 비교해서 가장 횟수가 적은 것을 계속해서 DP에 저장하면서
상향식으로 문제를 해결할 수 있을것이라는 생각이 들었다.
using System;
public class Solution {
//dp문제?
// dp[5] = dp[5 - n] + 1 or dp [5 / 2 ] + 1 or dp [5 / 3] + 1
public int solution(int x, int y, int n)
{
int[] dp = new int[y+1];
for(int i =0; i<y+1; i++){
dp[i] = -1;
}
dp[x] = 0;
for(int i= x+1; i <= y; i++)
{
int caculateN= int.MaxValue;
int caculate2= int.MaxValue;
int caculate3 = int.MaxValue;
if (i > n && dp[i-n] != -1)
{
caculateN = dp[i-n] + 1;
}
if (i % 2 == 0 && dp[i/2] != -1)
{
caculate2 = dp[i/2] + 1;
}
if (i % 3 == 0 && dp [i/3] != -1)
{
caculate3 = dp[i/3] + 1;
}
int min = Math.Min(caculateN, Math.Min(caculate2, caculate3));
if (min == int.MaxValue)
{
dp[i] = -1;
}
else{
dp[i] = min;
}
}
return dp[y];
}
}
만들수 없는 수들은 제외를 해야하기 때문에 배열을 먼저 -1로 초기화하고
시작수인 x에 0을 넣으면서 y까지 반복하면서 상향식으로 dp 배열을 채워나갔다.
만들지 못하는 수 즉, dp배열이 -1인 수는 무시하고 만들 수 있는 수라면
횟수를 +1 해서 저장하였고 3가지 방법중 가장 최적인 수를 계속해서 저장하여 문제를 해결했다.
