📙[Algo] 24.01.24 알고리즘

알고리즘 문제) BOJ 9007. 카누 선수

9007번: 카누 선수

문제 요약

• • n명으로 구성된 4개의 반이 주어짐
  • 각 반마다 학생들의 몸무게가 주어짐
  • 반 별 1명씩 선출하여, 몸무게 합이 k에 근사한 경우 찾기
  • 만약 여러 개 있을 경우 더 가벼운 걸 선택

시간 제한

• 3초

입력

• T 테스트케이스
• 테스트 케이스별 k, n
  • 1≤k≤4000만
  • 1≤n≤1000
• 테스트 케이스별 각 반의 학생들 몸무게가 n개씩 주어짐
  • 1~1000만

출력

• 지목된 학생들의 몸무게 총합?

접근법

1. 완전 탐색으로 접근하기
   • 4중 for문을 활용하여 모든 경우를 탐색한다.
   • 100010001000*1000 ⇒ 시간초과 → 최대 2번까지만 쓸 수 있음
2. 최적화 하기
   • 1반+2반 / 3반+4반 각각 학생들별로 몸무게를 합친 배열을 하나 만든다.
   • 그럼 각 두반씩 몸무게를 합친 배열 두개가 생성된다.
     • 각 배열을 오름차순 정렬
     • arr1의 포인터는 0인덱스(가장 작은 친구), arr2의 포인터는 끝 인덱스(가장 큰 친구)를 가리킨다.
       • 둘이 더하면서 k값에 근접한 값을 찾아간다.
         • 매 케이스마다 무게합 최솟값으로 갱신
         • 만약 sum > K, e-=1;
         • 아니면 s+=1;
     103, 108, 115, 115, 120, 123, 127, 128, 128, 135, 140, 143, 148, 148, 155, 168
     s
     97, 97, 103, 104, 104, 110, 121, 121, 123, 123, 127, 129, 142, 149, 166, 168
                                                                                                                           e
     
     • s→103, e→168
       • sum : 271
       • 300과의 차이를 좁히기 위해 271보다 커여하는데, 현재 가장 큰 e를 더한 것이므로 s+=1
     • s→108, e→ 168
       • sum : 276
       • s+=1
     • s→115, e→168
       • sum : 283
       • s+=1
     • s→ 115 ⇒ s+=1
     • s→ 120, e→168
       • sum : 288
       • s+=1
     • s→ 123, e→168
       • sum ; 291
       • s+=1
     • s→ 127, e→168
       • sum : 295
       • s+=1
     • s→ 128, e→168
       • sum : 296
     • s→128 ⇒ s+=1
     • s→ 135, e→168
       • sum : 303
       • e-=1
     • s→ 135, e→ 166
       • sum : 301
       • minDiff : 1
       • e-=1
     • s→ 135, e→ 149
       • sum : 284
       • s+=1
     • s→ 140, e→ 149
       • sum : 289
       • s+=1
     • s→ 143, e→149
       • sum : 291
       • s+=1
     • s→ 148, e→149
       • sum : 297
       • s+=1
     • s→ 155, e→ 149
       • sum : 304
       • e-=1
     • s→ 155, e→ 142
       • sum : 297
       • s+=1
     • s→ 168, e→ 142
       • sum : 310
       • e-=1
     • s→ 168, e→ 128
       • sum : 296
       • s+=1 ⇒ 배열 범위 벗어나므로 종료
     ⇒ 종료 조건 : s≥배열크기(N*N) 또는 e<0

고민

• 최소값이 같아도 합계가 더 작은 애로 갱신해야하는데, 그 부분을 아래처럼 구현하니까 틀렸다. 왜일까?? 작은애가 먼저 기록되면 그 후에 갱신이 안되니까?

if (minDiff >= Math.abs(sum - k)) {
	  minDiff = Math.abs(sum - k);
	  if(answer > sum) answer = sum;
}

 

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        int k, n, s, e, sum, minDiff, answer;
        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            k = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());

            int[][] students = new int[4][n];
            for (int i = 0; i < 4; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    students[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            int[] arr1 = new int[n*n];
            int[] arr2 = new int[n*n];
            for (int i = 0, idx = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    arr1[idx] = students[0][i] + students[1][j];
                    arr2[idx++] = students[2][i] + students[3][j];
                }
            }

            Arrays.sort(arr1);
            Arrays.sort(arr2);

            s = 0;
            e = n * n - 1;
            sum = 0;
            minDiff = Integer.MAX_VALUE;
            answer = Integer.MAX_VALUE;
            while (0 <= e && s < n * n) {
                sum = arr1[s] + arr2[e];

                if (minDiff > Math.abs(sum - k)) {
                    minDiff = Math.abs(sum - k);
                    answer = sum;
                } else if (minDiff == Math.abs(sum - k)) {
                    answer = Math.min(answer, sum);
                } 

                if(sum < k) s++;
                else e--;
            }

            sb.append(answer+"\n");
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 7453. 합이 0인 네 정수

7453번: 합이 0인 네 정수

문제 요약

• 배열 크기 N인 배열 A, B, C, D 존재
• A[a] + B[b] + C[c] + D[d] = 0인 쌍의 개수 구하기

시간 제한

• 12

입력

• 배열 크기 n (1≤n≤4000)
• 배열에 포함되는 정수가 공백으로 구분되어 주어짐
  • A[0] B[0] C[0] D[0]
  • …
  • A[N-1] B[N-1] C[N-1] D[N-1]

출력

• 합이 0이 되는 쌍의 개수

접근법

1. 완전 탐색으로 접근하기
   • 4중 for문을 만들어서 모든 경우를 체크하고, 합이 0인 경우 카운트한다.
   • 400040004000*4000 ⇒ 시간초과
2. 최적화하기
   • 카누 문제처럼 접근하면 될 것 같다.
   • A와B, C와D 각각의 무게들을 합친 배열을 두 개만들어서 투포인터로 합이 0이되는 지점 찾기!

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

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

        int n = Integer.parseInt(br.readLine());
        long[][] arr = new long[n][4];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
            arr[i][2] = Integer.parseInt(st.nextToken());
            arr[i][3] = Integer.parseInt(st.nextToken());
        }

        long[] sumArr1 = new long[n*n];
        long[] sumArr2 = new long[n*n];
        for (int i = 0, idx = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sumArr1[idx] = arr[i][0] + arr[j][1];
                sumArr2[idx++] = arr[i][2] + arr[j][3];
            }
        }

        Arrays.sort(sumArr1);
        Arrays.sort(sumArr2);

        int s = 0, e = n * n - 1;
        long sCnt, eCnt, cnt = 0, sum = 0;
        while (s < n * n && 0 <= e) {
            sum = sumArr1[s] + sumArr2[e];

            if (sum < 0) {
                s++;
            } else if (sum > 0) {
               e--;
            } else {
                sCnt = 1;
                while (s + 1 < n * n && sumArr1[s + 1] + sumArr2[e] == 0) {
                    sCnt++;
                    s++;
                }
                s++;

                eCnt = 1;
                while (0 <= e - 1 && sumArr1[s - 1] + sumArr2[e - 1] == 0) {
                    eCnt++;
                    e--;
                }
                e--;

                cnt += sCnt * eCnt;
            }
        }


        bw.write(String.valueOf(cnt));
        bw.flush();
        bw.close();
        br.close();
    }
}