글 읽기 - 반례나 틀린부분 간절하게 고대합니다..

huh0918 2년 전 0

웬만한 테스트 케이스는 다 통과했는데 어디가 문제인지 모르겠습니다 ㅜ

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int t, n, m;

int main()
{
    cin >> t;
    while (t--) 
    {
        cin >> n >> m;
        vector<vector<long long>> dp(n+1, vector<long long>(m+1,0));
        // dp[n][m] : n번째 자리수에 m이 마지막 숫자로 오는 경우의 수
        // n=4인 경우의 정답은 dp[4][i]들을 전부 더하면 됨
        // 예제의 경우, dp[4][8] = 1, dp[4][9]=1, dp[4][10]=2
        // 합해서 4가 정답. 나머지는 0이됨
 
 /*
 i번째 자리에 올 수 있는 1~m의 수는 최소 2^(i-1) 보다 크고 
 m/(2^(n-i)) 보다 작다.
 예제 : n=4, m=10의 경우, 
 첫번째 자리에 올 수 있는 수는 1 뿐이다. (2^0 ~ 10/8=)
 두번째 자리에 올 수 있는 수는 2 뿐이다. (2^1 ~ 10/4)
 세번째는 4, 5 (2^2 ~ 10/2)
 네번째는 8,9,10 (2^3 ~ 10/1)
 이러한 수학적 사실을 이용해서 시간복잡도를 절약
 */
        
        // 첫번째 자리에 올 수 있는 경우의수 우선 채우기
        int start_m = 1;
        int max_m = m / (int)pow(2, n - 1);
        for (int j = 1; j <= max_m; j++) {
            dp[1][j] = 1;
        }

        // 관계를 이용해서 바텀업으로 쭉 채워나가기
        /*
        점화식은 다음과 같다.
        예제를 이용하면, 
        dp[4][8] = dp[3][4] = 1 (3번째 자리까지 4와 5로 채운게 있지만, 4인 경우에만 8이 올 수 있음.)
        dp[4][9] = dp[3][4] = 1 (4번째 자리에 9가 오는 경우도 마찬가지로, 3번째 자리에 4가 오는 경우만 가능)
        dp[4][10] = dp[3][4] + dp[3][5] (3번째 자리에 4, 5 두 수중 어느수가 와도 10 가능)
        즉, dp[n][j]는 dp[n-1][k]들을 더한 값이다 ( 2^n-2 <= k <= j/2)
        */
        for (int i = 2; i <= n; i++) 
        { 
            start_m *= 2; // 2^i-1 부터
            max_m = m / (int)pow(2, n - i); // m/2^n-i 까지만 채우고 나머지둠
            for (int j = start_m; j <= max_m; j++) 
            {
                int prev_max_m = j / 2;
                for (int k = start_m/2; k <= prev_max_m; k++) {
                    dp[i][j] += dp[i - 1][k];
                }
            }
        }

        long long result = 0;
        for (long long i : dp[n]) {
            result += i;
        }
        cout << result;
    }

    return 0;
}

jinhan814 2년 전 1

개행문자를 출력하지 않는게 문제인 거 같습니다.

64번줄을 cout << result << '\n';으로 바꾸시면 될 거 같아요

huh0918 2년 전 1

ㅎㅎ.. 허무하네요 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례나 틀린부분 간절하게 고대합니다..

huh0918 2년 전 0

jinhan814 2년 전 1

huh0918 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말