[JAVA] 백준 1253 좋다

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

1253번: 좋다

 

1. 서론

 

아직 이 문제를 안 풀었다면 다른 문제를 풀었으면 좋겠다. (설명이 불친절한 수준을 넘어서 힌트를 찾아보지 않으면 풀 수가 없음)

 

**힌트:  합을 구하고 그게 N과 같다고 가정할 때 N은 합을 구하는 두 수에 포함되면 안 됨.**

 

제 아무리 문제를 푸는 방법이 여러 가지라지만 나처럼은 풀면 안 된다... (심지어 풀면서 터지겠지만 그냥 해보자....라고 생각했음)라는 걸 느끼게 해 준 문제.

 

나는 조합으로 풀었는데 시간은 당연히 더럽게 오래 걸렸고, 후에 다른 사람 코드를 보고 '투 포인터'의 풀이법을 알게 되었다.

 

 

2. 문제 설명

 

n개의 배열이 주어진다. 이 중 두 개의 합이 n개의 배열에 존재한다면 그 수를 '좋다'라고 할 수 있다. 이 '좋다'라고 할 수 있는 수가 몇 개가 있나 구하는 문제이다. n개 중 같은 값이 나와도 그 값은 별개로 치는 게 문제의 조건이다. 그리고 서론에 적은 힌트를 적용하지 않으면 문제를 풀 수가 없다.

 

문제 자체는 매우 간결한데 문제가 간결할수록 푸는 법이 어려운 법. 처음에 딱 생각난 방법은 n개 중 두 개를 뽑아서 합을 구하는 것이다. 하지만 분명 아무리 조합이라도 모든 경우의 수를 다하면 시간이 터질 거라고 생각했지만 다른 방법은 생각나지 않았다.

 

처음에는 힌트 부분을 생각지 못해서 틀렸었는데 힌트 부분을 구현하고 visit으로 방문처리해서 반복 횟수를 줄여주니 아슬아슬하게 맞았다. 그러나 2초가 리밋인데 1696ms로 시간이 너무 오래 걸렸고, 맞기는 했지만 역시나 이렇게 푸는 게 아니구나 깨닫고 방법을 찾아보게 되었다.

 

 

+ 조합으로 통과한 코드

 

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

public class Main {

    static int[] a, select;
    static boolean[] visit;
    static int n, ans = 0;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        a = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            a[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(a);

        select = new int[2];
        visit = new boolean[n + 1];
        comb(0, 0);
        System.out.print(ans);

        bw.flush(); bw.close(); br.close();
    }

    public static void comb(int idx, int cnt) {
        if (cnt == 2) {
            int sum = a[select[0]] + a[select[1]];
            for (int i = 0; i < n; i++) {
                if (a[i] == sum && i != select[0] && i != select[1]) {
                    if (!visit[i]) {
                        ans++;
                        visit[i] = true;
                    }
                    else return;
                }
            }
            return;
        }

        for (int i = idx; i < n; i++) {
            select[cnt] = i;
            comb(i + 1, cnt + 1);
        }
    }

}

 

방문처리 관련해서 가지치기가 잘 되었기 때문에 아슬아슬하게 통과한 듯.

 

 

3. 코드 설명

 

https://komas.tistory.com/75

[백준] 1253번 좋다 (JAVA)

 

 

이 블로그를 보고 투 포인터를 따라 했다.

 

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] a = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            a[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(a);

        int ans = 0;
        for(int i = 0;i < n; i++) {
            int x = a[i];

            int s = 0, e = a.length - 1, sum = 0;
            while (s < e) { //시작 < 끝
                sum = a[s] + a[e];
                if (sum == x) { //'좋다'인 수 중에
                    if (i == s) //시작점이 현재 값일때 (cnt 안함)
                        s++;
                    else if (e == i) //끝점이 현재 값일때 (cnt 안함)
                        e--;
                    else {
                        ans++;
                        break;
                    }
                }
                if (a[s] + a[e] > x) // 값이 크면 작은 값으로 이동해서 값 맞춤
                    e--;
                else if (a[s] + a[e] < x) //값이 작으면 큰 값으로 이동해서 값 맞춤
                    s++;
            }
        }
        System.out.print(ans);

        bw.flush(); bw.close(); br.close();
    }
}

 

배열을 정렬해 놓고 값이 작으면 포인터를 큰 쪽으로 옮겨서, 작으면 작은 쪽으로 옮겨서 값을 '좋다'에 맞게 맞춰준다.

여기서도 마찬가지로 가리키고 있는 두 값이 합과 같으면 안 된다는 것이 포인트다.

 

일단 풀어서 Unsolved에 넣지는 않았는데 안 푼 거랑 다름없기는 하다...^^

투 포인터를 많이 안 풀어서 그런지 투 포인터의 개념 자체는 이해가 가는데 스스로 코드를 짜기에는 아직 부족하다.