[백준 - 5624번] 좋은 수 - Java

문제 링크

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

문제

티어: 골드 3
알고리즘: dp
정수 N개로 이루어진 수열 A가 있다. 이때, i번째 수가 그 앞에 있는 수 세 개의 합으로 나타낼 수 있을 때, 그 수를 좋다고 한다. (같은 위치에 있는 수를 여러 번 더해도 된다)

수열이 주어졌을 때, 총 몇 개의 수가 좋은 수 일까?

입력

첫째 줄에 수열 A의 크기 N이 주어진다. (1 ≤ N ≤ 5000) 둘째 줄에는 수열 A의 각 숫자가 공백으로 구분되어 주어진다. (-100,000 ≤ Ai ≤ 100,000)

출력

첫째 줄에 좋은 수의 개수를 출력한다.

풀이

수열에서 좋은 수의 개수를 출력해야 한다.

i번 째가 좋은 수인지 체크하는 경우의 수는

• 앞의 요소 중 같은 수를 3번 더한 경우
• 앞의 요소 중 하나의 수와 나머지 두 수를 더한 경우

예를 들어
6
1 2 3 5 7 10일 때

2번 째 인덱스인 3이 좋은 수인지 알려면
먼저, 0부터 i - 1까지 탐색한다. (1 2)

1) 0번 째 인덱스 (같은 수 3번)
arr[0] * 3과 3을 비교해서 같아면 좋은 수다.
만약 같지 않다면

2) 0번 째 인덱스의 수 한 번과 나머지 두 수의 합
arr[2] - arr[0] -> 이 값을 가진 두 수의 합이 있는지 체크한다. 있으면 좋은 수다.

1번과 2번 조건을 만족하지 않는다면 좋은 수가 아니다.

그러면 필요한건 두 수의 합이라는 것을 알 수 있다.

두 수의 합을 구하는 경우의 수는 5000 * 5000이기 때문에 충분히 가능하다.

그렇지만 처음부터 두 수의 합을 구하는 방식은 안된다. 왜냐하면 i 번째가 좋은 수인지 판단할 때 앞의 요소로만 판단하기 때문이다. 그래서 수열의 요소를 탐색하면서 채워나가야 현재 상태를 반영할 수 있다.

정리하자면, 각 요소를 돌면서 좋은 수인지 체크하기 위해 앞의 요소로 두 수의 합을 구한다.
그리고 0번째 인덱스 부터 i - 1 인덱스까지 탐색하면서 1, 2번 경우로 좋은 수인지 판단한다.

이 풀이의 시간 복잡도는 O(N^2)이다.

소스 코드

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

public class Main {
    static int N;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      
      int[] arr = new int[N]; // 수열
      StringTokenizer st = new StringTokenizer(br.readLine());
      
      for(int i=0; i<N; i++) {
          arr[i] = Integer.parseInt(st.nextToken());
      }
      
      HashMap<Integer, Boolean> vDp = new HashMap<>(); //2개의 조합을 체크할 용도로 HashMap 사용
      int cnt = 0;
      for(int i=1; i<N; i++) {
          for(int j=0; j<=i - 1; j++) {
              vDp.put(arr[j] + arr[i - 1], true); //2개의 조합을 넣어준다.
          }
          
          for(int j=0; j<=i - 1; j++) {
              //이제 가능한지 체크
              if((arr[j] * 3 == arr[i])) {
                  //같은 수 3번 더하는 경우
                  cnt += 1;
                  break;
              }
              //현재 수 한 번 2개 조합 중 한 번
              int left = arr[i] - arr[j];
              if(vDp.get(left) != null) {
                  cnt += 1;
                  break;
              }
          }
      }
      
      System.out.println(cnt);
  }
}