📙[Algo] 24.02.13 알고리즘

알고리즘 문제) BOJ 20159. 동작 그만. 밑장 빼기냐?

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

문제 요약

• N개의 카드와 2명의 플레이어
  • N은 짝수개가 주어짐
• 카드를 분배했을 때 카드 윗장에 적힌 수의 합이 더 큰 사람이 이김
  • 카드는 분배한 사람부터 받는다.
• 한번만 밑장 빼기를 할 때 얻을 수 있는 최대 카드 합?
  • 밑장 빼기 : 윗장이 아닌 밑장을 보여

시간 제한

• 2초

입력

• 카드 개수 N
  • 2≤N≤10만, 짝수
• 카드의 윗장부터 밑장까지 카드의 값 X가 정수로 주어짐
  • 1≤X≤1만

출력

• 정훈이가 얻을 수 있는 최대 카드 합?

접근법

• 밑장빼기 이해가 어려웠던 문제.. ⇒ 잘 못 이해하고 풀어서 틀림;;;;
• 해당 턴에서 밑장을 빼면 밑장에 있는 카드를 해당 턴에 받게 되고, 그만큼 카드가 밀리게 됨 ⇒ 즉 원해 홀수번째 받아야했다면 밑장뺴는 순간부턴 짝수번째를 받게 된다.

3 2 5 2 1 3

• 밑장 빼기 안 할 경우
  • 정훈 : 3 5 1 (1, 3, 5)
  • 상대 : 2 2 3 (2, 4, 6)
• 1 턴에서 밑장 빼기
  • 정훈 : 3 2 2 (6, 2, 4)
  • 상대 : 5 1 3 (3, 5, 1)
• 2턴에서 밑장 빼기(상대방)
  • 정훈 : 3 2 2 (1, 2, 4)
  • 상대 : 3 5 1(6, 3, 5)
• 3턴에서 밑장 빼기
  • 정훈 : 3 3 2(1, 6, 4)
  • 상대 : 2 5 1(2, 3, 5)
• 4턴에서 밑장 빼기
  • 정훈 : 3 5 2 (1, 3, 4)
  • 상대 : 2 3 1 (2, 6, 5)
• 5턴에서 밑장 빼기
  • 정훈 : 3 5 3 (1, 3, 6)
  • 상대 : 2 2 1 (2, 4, 5)

⇒ 밑장빼기를 했을 때

• 밑장빼기를 안 할수도 있으니까 answer 값 초기값은 밑장빼기를 안 했을 때로 초기화
• 정훈이 차례에서 밑장 뺐을 경우
  • 그 전까지는 홀수번째 카드를 받고,
  • 해당 차례에서 N번째 카드(밑장)을 받고,
  • 그 이후에는 짝수번째 카드를 받는다.
  • ⇒ odd[i-1] + arr[N] + even[N] - even[i-1]
• 상대방 차례에서 밑장 뺐을 경우
  • 그 전까지는 홀수번째 카드를 받고,
  • 해당 차례부터는 짝수번째 카드를 받는다.
  • ⇒ odd[i-1] + even[N] - even[i-1]

코드

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

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

        int[] odd = new int[N + 1];
        int[] even = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            if (i % 2 == 1) {
                // 홀수 번째
                odd[i] = odd[i - 1] + Integer.parseInt(st.nextToken());
                even[i] += even[i - 1];
            } else {
                // 짝수 번째
                even[i] = even[i - 1] + Integer.parseInt(st.nextToken());
                odd[i] += odd[i - 1];
            }
        }

        int answer = odd[N - 1];
        for (int i = 1; i < N; i++) {
            if (i % 2 == 1) {
                // 정훈이 차례 밑장 빼기
                answer = Math.max(answer, odd[i - 1] + even[N] - even[i - 1]);
            } else {
                // 상대방 차례 밑장 빼기
                answer = Math.max(answer, odd[i - 1] + even[N - 1] - even[i - 1]);
            }

        }

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

 

알고리즘 문제) BOJ 22945. 팀 빌딩

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

문제 요약

• 개발자 N명이 팀빌딩을 위해 한 줄로 서있다.
• 팀의 능력치
  • (개발자 A와 개발자 B 사이에 존재하는 다른 개발자 수) * min(개발자 A의 능력치, 개발자 B의 능력치)
• 나올 수 있는 팀 중 능력치 최대값?

시간 제한

• 1초

입력

• 개발자수 N
  • 2 ≤ N ≤ 10만
• 능력치 xi가 공백으로 주어짐
  • 1 ≤ xi ≤ 1만, xi는 정수

출력

• 팀의 능력치 최대값?

접근법

1. 완전 탐색으로 접근하기
   • 2중 for문 사용해서 시작점(개발자A)과 끝점(개발자B)을 정한다.
   • ⇒ 그러나 N이 10만까지 가능하기 때문에 불가능
2. 최적화 (투 포인터)
   • 1 4 2 5
     s       e
   • 팀 능력치는 두 가지를 고려해야 함
     1. A,B사이에 존재하는 개발자 수
     2. min(개발자A 능력치, 개발자B 능력치)
   • s→1, e→N을 가리킨 상태에서 시작한다
     • 즉 1번 항목이 최대가 되는 경우 부터 시작
   • 그 다음은 능력치에 따라 결과 값이 바뀐다. 개발자수의 경우 더 작아질일밖에 없음
     • 그러면 능력치가 작은쪽을 더 키우는 방향으로 가야함
       • arr[s] < arr[e] 라면 s+=1
       • arr[s] ≥ arr[e] 라면 e-=1

코드

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

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

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

        int s = 0, e = N - 1;
        int answer = 0;
        while (s <= e) {
            answer = Math.max(answer, (e - s - 1) * Math.min(arr[s], arr[e]));

            if(arr[s] < arr[e]) s++;
            else e--;
        }

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

 

알고리즘 문제) BOJ 27172. 수 나누기 게임

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

문제 요약

• 모든 플레이어가 본인을 제외한 다른 플레이어와 한 번씩 결투를 해야 끝난다.
• 게임은 아래와 같이 진행
  • 1~100만사이 수가 적힌 카드들을 한 장씩 나눠 가짐
  • 플레이어끼리 서로 카드를 보여줬을 때 상대방 카드 % 본인 카드가 0이면 승리
    • 승리 : +1
    • 패배 : -1
    • 무승부 : 변화 X
• 게임 종료 후 모든 플레이어의 점수 구하기

시간 제한

• 1초

입력

• 플레이어 수 N
  • 2≤N≤10만
• N번째 플레이어까지 각 카드에 적힌 정수가 공백으로 주어짐 xi
  • 1 ≤ xi ≤ 100만
  • 중복된 수 X

출력

• 각 플레이어의 점수를 공백으로 구분해 출력

접근법

1. 완전 탐색으로 접근하기
   • 2중 for문을 사용해서 플레이어끼리 비교한다.
   • ⇒ 하지만 N이 10만까지 가능하기 때문에 for문은 1개만 사용 가능
2. 최적화 하기
   • 우선 1000000크기의 배열을 만든다. (check, score)
     • check : 현재 숫자 카드 존재 여부 체크
     • score : 점수 기록
   • 입력 받을 때마다 check[x] = true; 를 진행한다.
   • for문을 통해 x를 순회하면서
     • x의 약수를 구한다
       • if(check[약수])
         • score[x] += -1
         • score[약수] += +1
     ⇒ 약수 구할 때도 최적화 진행(제곱근까지만)

코드

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

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

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

        int num;
        int[] score = new int[1000010];
        for (int i = 0; i < N; i++) {
            num = arr[i];

            // 약수 구하기
            for (int j = 1; j * j <= num; j++) {
                if (num % j == 0) {

                    if (check[j]) {
                        score[num] += -1;
                        score[j] += +1;
                    }

                    if (j * j != num) {
                        // 중근이 아닐 경우
                        if (check[num / j]) {
                            score[num] += -1;
                            score[num / j] += +1;
                        }
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append(score[arr[i]]+" ");
        }

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

 

알고리즘 문제) BOJ 9763. 마을의 친밀도

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

문제 요약

• 마을의 좌표
  • (x, y, z) 형태
• 마을 중 세 마을의 친밀도
  • d12 + d13
    • dij = abs(xi-xj) + abs(yi-yj) + abs(zi-zj)

시간 제한

• 1초

입력

• 마을의 수 N
  • 3 ≤ N ≤ 1만
• N개의 줄에 마을의 위치 (x,y,z)가 주어짐
  • -1000 ≤ x,y,z <+ 1000

출력

• 친밀도 중 가장 작은 값 출력

접근법

1. 완전 탐색으로 생각하기
   • 전체 마을 중 3개를 선택하는 모든 경우의 수에서 친밀도 계산하기
     • 3중 for문 ⇒ 그러나 최악의 경우 100001000010000으로 시간초과
     • ⇒ for문은 최대 2개까지만 사용 가능
2. 최적화 하기
   • x좌표 차이, y좌표 차이, z좌표 차이
   • 우선 마을 좌표를 오름차순 정렬
     • x좌표 우선 정렬
     • x좌표 같으면 y좌표 정렬
     • y좌표 같으면 z좌표 정렬
   • 2중 for문을 사용해서 마을1, 마을2의 가장 작은 친밀도를 찾는다.
     • 만약 더 작은 친구가 나오면 원래 저장해둔 친밀도는 d2에 저장하고 더 작은 친구는 d1에 저장한다.

코드

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

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

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

        int d1, d2, dist, answer = Integer.MAX_VALUE;
        for (int i = 1; i <= N; i++) {
            d1 = 10000;
            d2 = 10000;
            dist = 10000;
            for (int j = 1; j <= N; j++) {
                if(i != j){
                    dist = Math.abs(town[i][0]-town[j][0]) + Math.abs(town[i][1]-town[j][1]) + Math.abs(town[i][2]-town[j][2]);

                    if (d1 > dist) {
                        d2 = d1;
                        d1 = dist;
                    } else if (d2 > dist) {
                        d2 = dist;
                    }
                }
            }
            answer = Math.min(answer, d1 + d2);
        }

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

 

알고리즘 문제) BOJ 14476. 최대공약수 하나 빼기

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

문제 요약

• 정수 A가 B로 나누어떨이지면, B는 A의 약수이며 A는 B의 배수
• 최대공약수란 공통 약수 중 가장 큰 수
• N개의 정수 중 임의의 수 K를 뺐을 때, 나머지 N-1개의 최대공약수가 가장 커지는 것 찾기
  • 이때 최대 공약수가 K의 약수면 안 됨

시간 제한

• 2초

입력

• 정수의 개수 N
  • 4 ≤ N ≤ 100만
• N개의 수가 주어짐
  • 20억을 넘지 않는 자연수

출력

• 정수 하나를 빼서 만들 수 있는 가장 큰 최대 공약수와 뺀 수를 공백을 두고 출력
• 없다면 -1

접근법

• 뽑는 숫자 위치 기준(i)으로 1~(i-1)까지 GCD와 (i+1)~N까지 GCD의 GCD를 구하고, K % GCD ≠ 0인 경우를 찾아서 최댓값으로 갱신한다.
• 이때, 미리 prefix, sufix 방향의 GCD를 기록한 배열을 만들고 사용하기(구간 → 점)

코드

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

public class Main {

    static int getGCD(int a, int b) {

        int tmp;
        while (b != 0) {
            tmp = a % b;
            a = b;
            b = tmp;
        }

        return a;
    }

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

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

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

        int[] prefix = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            prefix[i] = getGCD(Math.max(prefix[i - 1], arr[i]), Math.min(prefix[i - 1], arr[i]));
        }

        int[] suffix = new int[N + 2];
        for (int i = N; i >= 1; i--) {
            suffix[i] = getGCD(Math.max(suffix[i + 1], arr[i]), Math.min(suffix[i + 1], arr[i]));
        }

        int k, gcd, ansGcd = -1, ansK = 0;
        for (int i = 1; i <= N; i++) {
            k = arr[i];
            gcd = getGCD(Math.max(prefix[i - 1], suffix[i + 1]), Math.min(prefix[i - 1], suffix[i + 1]));
            if (k % gcd != 0) {
                ansGcd = Math.max(ansGcd, gcd);
                ansK = k;
            }
        }

        if (ansGcd != -1) {
            bw.write(String.valueOf(ansGcd + " " + ansK));
        } else {
            bw.write(String.valueOf(ansGcd));
        }

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

 

알고리즘 문제) BOJ 24523. 내 뒤에 나와 다른 수

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

문제 요약

• 길이가 N인 수열 A1~AN
• 1≤i≤N인 정수 i마다
  • i<j≤N이고,
  • Ai ≠ Aj인 정수 j중 최솟값 출력하기
  • 없다면 -1 출력

시간 제한

• 1초

입력

• 수열 크기 N
  • 1≤N≤100만
  • Ai : 10억 ~ 10억
• 수열 A가 공백으로 구분되어 주어진다.

출력

• 각 i마다 조건을 만족하는 최솟값 j 출력
  • 없다면 -1

접근법

1. 완전탐색으로 접근하기
   • 2중 for문으로 비교 ⇒ 하지만 N이 100만까지 이기때문에 for문을 한 번만 쓸 수 있다.
2. 최적화하기
   3 3 3 2 2 3 1 1 4 4 3 2 3 4
   • i = 1, start = 1, cnt = 1
     • arr[i] == arr[i+1]이므로, cnt += 1
   • i = 2, cnt = 2
     • arr[i] == arr[i+1] 이므로, cnt += 1
   • i = 3, cnt = 3
     • arr[i] ≠ arr[i+1] 이므로, 인덱스 start부터 start+cnt-1까지 arr[i+1]을 기록해야한다.
     • ⇒ 이 기록을 어떻게 해야 할까..?
     • ⇒ imos 생각해보기
     • i=1 → +(i+1)기록
     • i=4 → -(i+1)기록
     • … ⇒ N-1까지 진행하고 나서, 업데이트를 기록한 배열 구간합 진행 후 출력

코드

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));
        StringBuilder sb = new StringBuilder();

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

        int[] arr = new int[N + 1];

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

        long[] update = new long[N + 1];
        int start = 0, cnt = 0;
        for (int i = 1; i < N ; i++) {
            if (cnt == 0) {
                start = i;
                cnt = 1;
            }
            if (arr[i] == arr[i + 1]) {
                cnt++;
            } else {
                update[start] += i + 1;
                update[start + cnt] += -(i + 1);
                cnt = 0;
            }
        }

        for (int i = 1; i <= N; i++) {
            update[i] += update[i - 1];

            if(update[i] == 0) update[i] = -1;
        }

        for (int i = 1; i <= N; i++) {
            sb.append(update[i] + " ");
        }

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

 

알고리즘 문제) BOJ 23032. 서프라이즈~

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

문제 요약

• N명의 학생 1~N번 학번
• 먹고 싶은 스테이크 그램 조사
• 다음 조건에 따라 이벤트 진행
  • 임의로 연속된 학번의 학생들 선택
  • 임의로 대상 학생들을 두 그룹으로 나눔
    • 그룹별로 학번이 인접해야 하며, 최소 1명 이상으로 구성
  • 두 그룹의 무게 합 차 E 구하기(큰 - 작)
  • E가 최솟값인 두 그룹이 당첨
    • 여러 개가 있다면 스테이크 무게 합이 가장 큰 두 그룹 당첨

시간 제한

• 1초

입력

• N
  • 2~2000
• 1번부터 N번 학생까지 적은 스테이크 무게 W
  • 1≤W≤10000

출력

• 이벤트에 당첨된 학생들의 스테이크 무게 합 출력

접근법

1. 완전 탐색으로 접근하기
   • 2중 for문으로 대상 그룹 선정 (시작점, 끝점)
     • for문을 이용해서 두 그룹을 구분할 기준점 선택
       • ⇒ 3중 for문이므로 시간 초과 뜸 ⇒ 최대 2중 for문만 쓸 수 있다.
2. 최적화하기
   • 합 ⇒ 누적합 배열로 미리 만들기
   • 그룹 나누기
     • 2중 for문으로 대상 그룹 선정
     • 이분탐색으로 두 그룹으로 나눈다.
       • group1 > group2
         • e = mid - 1
       • group1 ≤ group2
         • s = mid + 1

코드

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

public class Main {
    static int N;
    static int[] arr;
    static int ansDiff = Integer.MAX_VALUE;
    static int ansSum;

    static void binarySearch(int s, int e) {
        int mid, g1, g2, diff;
        int start = s, end = e;
        while (s <= e) {
            mid = (s + e) / 2;

            g1 = arr[mid] - arr[start - 1];
            g2 = arr[end] - arr[mid];

            diff = Math.abs(g1 - g2);

            if(ansDiff > diff){
                ansDiff = diff;
                ansSum = g1 + g2;
            } else if (ansDiff == diff) {
                if(ansSum < g1 + g2) ansSum = g1 + g2;
            }

            if (g1 > g2) {
                e = mid - 1;
            } else {
                s = mid + 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));

        N  = Integer.parseInt(br.readLine());

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

        for (int i = 1; i <= N - 1; i++) {
            for (int j = i + 1; j <= N; j++) {
                binarySearch(i, j);
            }
        }

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