[BOJ] 9095. 1, 2, 3 더하기

24 Jun 2019

Reading time ~2 minutes

[BOJ]1, 2, 3 더하기

[BOJ]1, 2, 3 더하기

http://boj.kr/9095

9명의 난쟁이 중 진짜 난쟁이 7명의 키의 합이 100일 때 일곱난쟁이를 찾아 그 키를 각각 출력하는 문제

N중 for문을 사용한 1, 2, 3 더하기

http://codeplus.codes/006055b814014702aa7abeded348e307

재귀함수로 구현한 1, 2, 3 더하기

재귀함수를 int형으로 하여 전역변수 없이 count 처리

//import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int T=sc.nextInt();
//		int arr[]=new int[3];
		for (int t = 0; t < T; t++) {
			int N=sc.nextInt();
			int cnt=go(0,0,N);
//			int cnt=go(0,0,arr,N);
			System.out.println(cnt);
		}
	}

	public static int go(int index,int sum,int N) {
//	public static int go(int index,int sum,int arr[],int N) {
		if(index==N) {
			if(sum==N) {
//				System.out.println(Arrays.toString(arr));
				return 1;
			}
			return 0;
		}

		if(sum==N) {
//			System.out.println(Arrays.toString(arr));
			return 1;
		}
		int count=0;
		for (int i = 1; i <= 3; i++) {
//			arr[index]=i;
			count+=go(index+1,sum+i,N);	//
//			count+=go(index+1,sum+i,arr,N);
//			arr[index]=0;
		}
		return count;
	}
}

코드정리 및 count 계산을 전역변수로 처리

import java.util.Scanner;

public class Main {
	static int cnt;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int T=sc.nextInt();
		for (int t = 0; t < T; t++) {
			cnt=0;
			int n=sc.nextInt();
			go(n,0);
			System.out.println(cnt);
		}		
	}

	public static void go(int n,int sum) {
		if(sum>n) {
			return;
		}
		else if(sum==n) {
			cnt++;
		}
		for (int i = 1; i <= 3; i++) {
			go(n,sum+i);			
		}
	}
}

DP로 구현한 풀이

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int [n];
		for(int i = 0; i < n; i++)
			arr[i] = sc.nextInt();		
		
		int[] dp = new int[11];
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;									
		
		for(int i = 4; i <= 10; i++)
			dp[i] = dp[i-3]+dp[i-2]+dp[i-1];
		
		for(int i = 0; i < n; i++)
			System.out.println(dp[arr[i]]);
	}
}

브루트포스 조합 DP