[백준 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 호출 - 재귀)