11057번: 오르막 수

문제접근🤔

1. 첫번째 풀이

   • DP를 2차원으로 두고 DP[수의 길이][첫자리숫자]를 나타내었다
   • DP에는 그 상태에서 가능한 오르막 수의 개수를 나타낸다

   

   • 위처럼 DP[][0]에는 전 행의 총합이 들어가게 되고, DP[][1]에는 전 열의 값에서 전 행의 전 열의 값을 빼주는 식으로 진행된다

     $$ DP[i][j] = DP[i][j-1] - DP[i-1][j-1] $$

   → 이런식으로 코드가 진행이 되면 오버플로우가 난 녀석과 뺄셈이 일어날때 음수의 값이 나오는 등 이상한 결과를 초래하게 된다

   #include <iostream>
   #include <vector>
   
   int n;
   std::vector<std::vector<long long> > dp;
   
   void input_setting()
   {
   	std::ios_base::sync_with_stdio(false);
   	std::cin.tie(0);
   	std::cout.tie(0);
   }
   
   void input()
   {
   	std::cin >> n;
   	dp.resize(n + 1, std::vector<long long>(10, 1));
   }
   
   void solution()
   {
   	long long sum;
   
   	sum = 10;
   
   	for (int i = 2; i <= n; i++)
   	{
   		dp[i][0] = sum;
   		for (int j = 1; j <= 9; j++)
   		{
   			dp[i][j] = (dp[i][j - 1] - dp[i - 1][j - 1]) % 10007;
   			sum = (sum + dp[i][j]) % 10007;
   		}
   	}
   	std::cout << sum % 10007;
   }
   
   int main(void)
   {
   	input_setting();
   	input();
   	solution();
   	return (0);
   }
   

   →라고 생각했는데 분기를 통해서 해결할 수 있었음(THANKS TO CHAN...SUHSHIN...NAJLEE)

   if (dp[i][j - 1] < dp[i - 1][j - 1])
               dp[i][j] = dp[i][j - 1] + 10007 - dp[i - 1][j - 1];
           else
               dp[i][j] = (dp[i][j - 1] - dp[i - 1][j - 1]);
           sum += dp[i][j] % 10007;
           sum %= 10007;
   

   • 이 구문에서 보면 +10007 이 조금은 뜬금없이 보일 수 있음
   • 현재 저 분기가 나온 이유는 예를들어 (10008 % 10007) - (10006 % 10007)의 경우 음수가 나오기 때문에 이런 경우 10008에 + 10007을 통하여 먼저 음수가 나올 상황을 없애주고 그 후에 % 10007을 해주면 원래 결과와 똑같기 때문

2. 두번째 풀이

   • 첫번째 풀이에서 뺄셈의 방식이 아닌 덧셈의 방식으로 풀이를 진행해봐야할듯

     

놓쳤던 부분😅

• 자료형 범위 초과로 인한 오버플로우로 잘못된 값을 출력하는 것에 대해서 인지를 하지 못했다
• dp[i][j]

코드😁

2160 KB

0 ms

#include <iostream>
#include <vector>

int n;
std::vector<std::vector<int> > dp;

void input_setting()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
}

void input()
{
    std::cin >> n;
    dp.resize(n + 1, std::vector<int>(10, 1));
}

void solution()
{
    long long sum;
    sum = 10;
    
    for (int i = 2; i <= n; i++)
    {
        dp[i][0] = sum;
        for (int j = 1; j <= 9; j++)
        {
        if (dp[i][j - 1] < dp[i - 1][j - 1])
            dp[i][j] = dp[i][j - 1] + 10007 - dp[i - 1][j - 1];
        else
            dp[i][j] = (dp[i][j - 1] - dp[i - 1][j - 1]);
        sum += dp[i][j] % 10007;
        sum %= 10007;
        }
    }
    std::cout << sum;
}

int main(void)
{
    input_setting();
    input();
    solution();
    return (0);
}