[백준 5557] 1학년 (자바)

 

https://www.acmicpc.net/problem/5557

5557번: 1학년

 

난이도 : 골드 5

 

전형적인 DFS 문제입니다.

가 아니고 DP 문제였습니다.

DFS로 풀었다가 시간 초과 났네요.

 

아무리 생각해도 DP로 풀 방법이 생각 안 나 검색해서 공부했습니다.

4

10 2 3 4 를 예로 들어보겠습니다.

 

 

이런 식으로 기존의 값에 +- n을 해주어 값을 최신화해줍니다.

이 예시의 출력은 0이겠네요.

단, 이 문제에서 수의 범위는 long형입니다. 이것을 주의하여 문제를 풀어야 합니다.

---

전역 변수 

n = 입력 숫자의 개수

number = 입력된 숫자

count = 계산을 한 후의 숫자 개수

메소드

void main 

입력을 받고 초기값(number[0])을 세팅해줍니다. 위에서 설명한 방법대로 DP를 진행합니다.

(cal 호출)

 

void cal

n-2번 반복합니다. n이 3일 때 계산은 1번만 이루어집니다.

새로운 long형 임시 배열을 생성하고 count 배열을 토대로 연산을 시작합니다.

연산이 끝나면 count에 임시 배열의 값을 덮어 씌워줍니다.

(cal 호출 - 재귀)

 

 

	import java.io.BufferedReader;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	public class p5557 {
	static int n, number[];
	static long count[] = new long[21];
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	n = Integer.parseInt(br.readLine());
	StringTokenizer stz = new StringTokenizer(br.readLine());
	number = new int[n];
	for(int i = 0; i < n; i++)
	number[i] = Integer.parseInt(stz.nextToken());
	count[number[0]] = 1;
	cal(0);
	System.out.println(count[number[n-1]]);
	}
	public static void cal(int index) {
	if(index == n-2)
	return;
	long temp[] = new long[21];
	for(int i = 0 ; i <= 20; i++){
	if(count[i] != 0) {
	if(i - number[index+1] >= 0)
	temp[i-number[index+1]] += count[i];
	if(i + number[index+1] <= 20)
	temp[i+number[index+1]] += count[i];
	}
	}
	count = temp.clone();
	cal(index+1);
	}
	}

view raw p5557.java hosted with ❤ by GitHub