📙[Algo] 24.03.04 ~ 24.03.05 알고리즘

알고리즘 문제) BOJ 2230. 수 고르기

• 링크 : https://www.acmicpc.net/problem/2230

문제 요약

• N개의 정수로 이루어진 수열 A[1], … A[N]이 존재
• 여기서 두 수를 골랐을 때, 그 차이가 M이상이면서 제일 작은 경우를 구해라
  • 같은 수를 고를 수도 있다.

시간 제한

• 2초

입력

• 두 정수 N, M
  • N개의 줄에 차례로 A[1], … A[N]이 주어진다.
  • 1≤N≤10만
  • 0≤M≤20억
  • 0≤abs(A[i])≤10억

출력

• 첫째 줄에 M이상이면서 가장 작은 차이 출력

접근법

1 2 3 4 5 6 (M=2)
s
e

1. s→ 1, e→1
   
   • abs(s,e) = 0 < M
   • e+=1
2. s→ 1, e→ 2
   • abs(s,e) = 1 < M
   • e+=1
3. s→ 1, e→ 3
   
   • abs(s,e) = 2 == M
   • 찾았으므로 break

⇒ 차이값 < M

• 더 큰 차이값을 찾아야 한다
• s기준 가장 작은 e와의 차이값을 구한 것이므로 e+=1

⇒ 차이값 > M

• 조건을 충족했으몰 정답 갱신
• 더 작은 차이를 찾아야 한다.
  • e기준 가장 큰 s와의 차이값을 구한 것이므로 s+=1

⇒ 차이값 == M

• 가장 최소가 될 차이값이므로 갱싱하고 break

코드

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

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;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        int s = 0, e = 0;
        int answer = Integer.MAX_VALUE;
        int diff;
        while (s <= e && e < N) {
            diff = Math.abs(arr[s] - arr[e]);
            if (diff >= M) {
                answer = Math.min(answer, diff);
                if (diff == M) break;
                s += 1;
            } else {
                e += 1;
            }
        }

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

 

알고리즘 문제) BOJ 1253. 좋다

• 링크 : https://www.acmicpc.net/problem/1253

문제 요약

• N개의 수 중 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다”라고 한다.
• N개의 수 중 좋은 수의 개수는 몇 개?
• 수의 위치가 다르면 값이 같아도 다른 수

시간 제한

• 2초

입력

• 수 N개
  • 1≤N≤2000
• i번째 수를 나타내나 Ai N개
  • Ai의 절대값은 10억이하

출력

• 좋은 수의 개수는?

접근법

1. 완전탐색으로 생각하기
   • 3중 for문을 돌면서 수 하나를 선택하고 남은 for문 2개로 다른 수들을 선택해서 합했을 때 해당 수가 되는 경우를 찾는다.
   • ⇒ 시간초과(for문은 최대 2개만 사용할 것)
2. 최적화 하기
   • for문 하나로 목표 수를 설정한다.
   • 그리고 투포인터 s, e를 사용해서 다른 두 수를 가리킨다.
   • 먼저 수열을 오름차순 정렬
   • 1 2 3 4 5 6 7 8 9 10
     s                e
   • s→ 1, e→10
     • arr[s]+arr[e] = 11 > 6
     • e-=1
   • s→1, e→9
     • arr[s]+arr[e] = 10 > 6
     • e-=1
   • s→1, e→8
     • arr[s]+arr[e] = 9 > 6
     • e-=1
   • s→1, e→7
     • arr[s]+arr[e] = 8 > 6
     • e-=1
   • s→1, e→6
     • arr[s]+arr[e] = 7 > 6
     • e-=1
   • s→1, e→5
     • arr[s]+arr[e] = 6 == 6
     • 찾음 ⇒ 카운트 증가하고 break;

• target > arr[s]+arr[e] : s+=1
• target < arr[s]+arr[e] : e-=1
• target == arr[s]+arr[e] : answer++

반례

5
0 0 0 0 1

• 현재 target 수는 s,e가 가리키면 안 된다 ⇒ 이게 제일 애먹었다
• 처음에 카운팅 배열 사용해서 푸니까 범위를 20억해서 메모리 초과 뜸
  • 그냥 카운트 변수를 개별적으로 만들고 같은 값을 가리키는 경우가 있다면 한 번 더 돌아서 카운트 변수가 2이상인 경우만 answer를 갱신하게 했다.

코드

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

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());

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        int target, s, e, sum;
        int answer = 0, cnt = 0;
        for (int i = 0; i < N; i++) {
            target = arr[i];
            s = 0;
            e = N - 1;
            cnt = 0;

            while (s < e) {

                sum = arr[s] + arr[e];

                if (sum > target) {
                    e--;
                } else if (sum < target) {
                    s++;
                } else {
                    if (target == arr[s] || target == arr[e]) {
                        cnt++;

                        if(cnt >= 2){
                            answer++;
                            break;
                        }

                        if(target == arr[s]) s++;
                        else if(target == arr[e]) e--;
                    } else {
                        answer++;
                        break;
                    }
                }
            }
        }

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

 

알고리즘 문제) BOJ 2613. 숫자 구슬

• 링크 : https://www.acmicpc.net/problem/2613

문제 요약

• N개의 숫자 구슬을 M개의 그룹으로 나누었을 때. 각 그룹의 합 중 최댓값이 최소가 되도록 하기
• 그 최댓값과 각 그룹을 구성하는 구슬의 개수 출력

시간 제한

• 1초

입력

• 구슬 개수 N, 그룹의 수 M
  • N은 300이하 자연수
  • M≤N(자연수)
• 구슬 숫자가 주어짐
  • 100이하 자연수

출력

• 각 그룹의 합 중 최댓값
• 각 그룹을 구성하는 구슬의 개수를 왼쪽부터 출력
• 둘 이상이면 하나만

접근법

1. 완전 탐색으로 접근하기
   • N개의 구슬을 M개의 그룹으로 나누려면 M-1개의 구분선이 필요하다.
   • 구분선의 번호를 내 좌측에 있는 구슬의 인덱스로 생각
   • 즉 1~N-1중 M-1개를 고르는 경우를 생각한다.
   • N은 300까지 가능하므로 N이 최대일 때 나올 수 있는 경우들은 300C0, 300C1, … , 300C299가 된다. ⇒ 경우의 수가 너무 많아지므로 다 보면 안 됨,,
2. 백트랙킹 가지치기
   • 만약, 그룹합이 현재까지 갱신한 최댓값의 최솟값보다 큰게 나온다면 가지치기 return

코드

• 시간 고려 안하고 완탐(백트) 돌린 코드

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

public class Main {
    static int N, M; // N: 구슬 개수, M : 그룹 개수
    static int[] marbles;
    static int[] selected;
    static int[] prefix;
    static int answer = Integer.MAX_VALUE;
    static int[] ansIdx;

    static void recur(int cur, int start) {

        if (cur > 1 && prefix[selected[cur - 1]] - prefix[selected[cur - 2]] >= answer) {
            return;
        }

        if (cur == M) {

            int max = 0;
            for (int i = 1; i <= M; i++) {
                max = Math.max(max, prefix[selected[i]] - prefix[selected[i - 1]]);
            }

            if (answer > max) {
                answer = max;
                for (int i = 1; i <= M; i++) {
                    ansIdx[i - 1] = selected[i] - selected[i - 1];
                }
            }

            return;
        }

        for (int i = start; i <= N - 1; i++) {
            selected[cur] = i;
            recur(cur + 1, i + 1);
        }

    }

    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;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        marbles = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            marbles[i] = Integer.parseInt(st.nextToken());
        }

        prefix = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            prefix[i] = prefix[i - 1] + marbles[i];
        }

        selected = new int[M + 1];
        selected[M] = N;
        ansIdx = new int[M];

        recur(1, 1);

        StringBuilder sb = new StringBuilder();
        sb.append(answer + "\\n");
        for (int idx : ansIdx) {
            sb.append(idx + " ");
        }

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