글 읽기 - 이 문제에 대한 접근법을 잘 모르겠습니다.

hpdong413 6년 전 0

저는 이 문제를 2의 멱수 값을 이용한 N을 목표로 하는 동전 교환 문제(다이나믹 프로그래밍)라고 생각했는데

답이 계속 틀렸다고 나옵니다... 혹시 제가 잘못 접근하고 있는 부분이 있을까요??

조언이나 힌트를 주시면 감사하겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		Scanner sc = new Scanner(in);

		int N = sc.nextInt();
		int R = 0;
		while(true) {
			int num = (int)Math.pow(2, R);
			if (num > N)
				break;
			R++;
		}
		
		int unitNumbers[] = new int[R];
		
		for (int a = 0; a < R; a++) {
			unitNumbers[a] = (int) Math.pow(2, a);
		}
		
		int[][] dynamicMap = new int[R + 1][N + 1];
		
		for (int a = 0; a < R + 1; a++) {
			dynamicMap[a][0] = 1;
		}
		
		for (int a = 1; a < N + 1; a++) {
			dynamicMap[0][a] = 0;
		}
		
		for (int a = 1; a < R + 1; a++) {
			
			for (int b = 1; b < N + 1; b++) {
				
				if (unitNumbers[a - 1] <= b) {
					dynamicMap[a][b] = dynamicMap[a - 1][b] % 1000000000 + dynamicMap[a][b - unitNumbers[a - 1]] % 1000000000;
				} else {
					dynamicMap[a][b] = dynamicMap[a - 1][b] % 1000000000;
				}
			}
		}
		
		for (int a = 0; a < R + 1; a++) {
			
			for (int b = 0; b < N + 1; b++) {
				System.out.print(dynamicMap[a][b] + " ");
			}
			System.out.println();
		}
		
		System.out.println(dynamicMap[R][N]);
		
		sc.close();
	}	
	
}

isangyoon 6년 전 1

DP로 접근하신 것은 틀린 것 없네요. AC 받은 소스 첨부해드립니다.

동전과 비슷하게 접근해서 풀었습니다.

1. 멱수를 저장한 후

2. 동전처럼 접근

3. DP로 점화식 계산

#include <iostream>
#include <algorithm>
#include <vector>

int main(int const argc, char const** argv)
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  int N;
  std::cin >> N;

  std::vector<long long> d(N + 1, 0);
  std::vector<long long> numbers;
  for (auto i = 1; i <= N; i <<= 1) numbers.push_back(i);

  d[0] = 1;
  for (auto i = 0; i < numbers.size(); ++i)
  {
    for (auto j = numbers[i]; j <= N; ++j)
    {
      d[j] = (d[j] + d[j - numbers[i]]) % 1000000000;
    }
  }

  std::cout << d[N] << std::endl;

  return 0;
}

hpdong413 6년 전 0

저도 다시 해봐야겠네요.. 감사합니다!

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

문제

문제

출처

ICPC

이 문제에 대한 접근법을 잘 모르겠습니다.

hpdong413 6년 전 0

isangyoon 6년 전 1

hpdong413 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말