[백준] 막대 만들기

[hye-on]

🔗 막대 만들기

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

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

using namespace std;


//dp

int N,Q;

int main() {
	cin >> N;
	
	vector<int>v(N);
	for (int i = 0; i <N; i++) {
		cin >> v[i];
	}
	
	cin >> Q;
	vector<int>arr(Q + 1);
	int maxN = 0;
	
	for (int i = 1; i <= Q; i++) {
		cin >> arr[i];
		maxN = max(arr[i], maxN);
	}

	vector<int>dp(100001);
	
	//자기 자신을 만드는 방법
	for (int i = 0; i < N; i++)
		dp[v[i]] = 1;
	
	for (int i = 1; i <= maxN; i++) {
		//i를 만드는 방법이 없음
		if (dp[i] == 0)
			continue;

		int num = i * 2;
		while (num <= maxN) {

			dp[num] += dp[i];  //i==2 -> 4, 6, 8, 10 | i== 3 ->  3. 6. 9. 12 
			num += i;
		}
	}
	
	for (int i = 1; i <= Q; i++) {
		cout << dp[arr[i]] << " ";
	}

}

코멘트

- 막대를 먼저고른다고 생각하니까 좀 어려웠던 것 같습니다.

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

import java.io.*;
import java.util.*;

/**
 * 21:55 시작!
 */
public class Main
{
	public static void main(String[] args) throws Exception {
	    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

	    int[] dp = new int[100_001]; // dp[i]는 i를 만드는 방법 수
	    int n = Integer.parseInt(bf.readLine());
	    st = new StringTokenizer(bf.readLine());
	    for(int i = 0; i < n; ++i) {
	        int length = Integer.parseInt(st.nextToken());
	        dp[length]++;
	    }

        for(int i = 1; i <= 50000; i++) {
            for(int j = 2; i * j <= 100_000; j++) {
                dp[i * j] += dp[i];
            }
        }
	    
	    int m = Integer.parseInt(bf.readLine());
	    st = new StringTokenizer(bf.readLine());
	    for(int i = 0; i < m; ++i) {
	        int target = Integer.parseInt(st.nextToken());
	        System.out.print(dp[target] + " ");
	    }
	    
	    
	}
}

코멘트

- 막대를 길이별로 카운팅하고, 특정 막대의 길이의 배수가 되는 수는 이 막대를 통해 만들 수 있으므로 방법에 +(해당 길이를 가진 막대의 수)를 하는 방식으로 풀이할 수 있습니다. (이때 target 값에 따라 중복되는 연산이 있을 수 있기 때문에 DP를 사용합니다!)