📙[Algo] 24.08.22 알고리즘

알고리즘 문제) BOJ 20960. Po

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

문제 요약

• 증강작업을 실시하여, 어떠한 수열을 만들었을 때, 최소 증강 횟수를 출력해라
  • 증강작업은 수열의 한 구간을 선택해 그 구간의 모든 요소를 특정 야ㅇ만큼 증가시킨 것을 의미한다.

시간 제한

• 1초

입력

• 수열의 길이를 나타내는 정수 n (1 ≤ n ≤ 100,000)
• n개의 0 이상 10^9 이하의 정수 ai
  • 증강 작업 이후의 수열을 의미

출력

• 가능한 최소 증강 작업 횟수인 m을 출력

접근법

• 특정 구간을 한번에 증가 시키면서 최소 횟수로 원하는 수열 형태를 만들어야함
• 예시로 다음과 같이 주어졌을 때
  • 1 3 4 2 5 2 1 2
    

    

  • 위 그림처럼 연속된 구간별로(색깔로 구분) 증가시키면 최소 횟수만큼만 연산을 수행할 수 있다.
  • 이때, 아래와 같은 특징을 뽑아낼 수 있는데,
    • 증가하는 구간은 한 번의 연산으로 해결 가능
      • 수열에서 증가하는 부분은 단일 구간으로 묶을 수 있다. 예를 들어, 숫자가 3에서 5로 증가할 때, 이 구간은 한 번의 증강으로 2만큼 증가시킬 수 있다.
      • 따라서 증가하는 구간은 해당 구간의 길이나 크기 차이와 상관없이 한 번의 연산으로 처리
    • 감소하는 구간이 있는 경우의 처리가 필요
      • 감소하는 구간이 생기면, 그 이전의 연산들이 영향을 받기 시작
      • 즉, 감소하는 값이 발생했을 때 해당 값을 기준으로 다시 작은 값까지 영향을 받아서 새로운 연산이 필요
        • ex) 1, 3, 4 로 계속 오름차순을 유지하다 감소하는 구간인 2을 만났다면
          • 이전 숫자인 4는 2보다 크기 때문에, 현재 높이에 영향을 줬다고 판단할 수 없으므로 연산 수행 X ⇒ 하지만, 그전에 2보다 작은 수자가 존재할 수 있으므로, 더 이전 숫자로 탐색 진행
          • 더 이전 숫자인 3은 2보다 크기 때문에, 현재 높이에 영향을 줬다고 판단할 수 없으므로 연산 수행 X ⇒ 하지만, 그전에 2보다 작은 숫자가 존재할 수 있으므로, 더 이전 숫자로 탐색 진행
          • 더 이전 숫자인 1은 2보다 작다 → 즉, 증가하는 구간을 찾게 되었으므로, 적어도 한 번은 연산을 수행해야한다고 판단할 수 있다

• 모노톤 스택 알고리즘 사용
  • 스택의 값들이 오름차순 형태로 유지되도록 했다.
    • 스택이 비어있다면 + 1
    • 비어있지 않다면, 현재 가리키는 요소와 크기 비교
      • 스택의 최상단 값이 현재 값보다 작다면 오름차순 형태이므로 + 1
      • 그게 아니라면, 현재 값보다 작거나 같은 값 만날때까 지 스택에서 pop 수행
        • 최종적으로 같은 값을 만난다면 따로 연산 수행 X
        • 만약 작은 값을 만난다면 마찬가지로 오름차순 구간이므로 + 1
• 원소가 0일 수 있으니 주의 → 전부 0인경우 따로 증가시킬 필요 없음 ⇒ 스택에 미리 0을 넣고 수행

코드

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

        // 스택 내부값이 오름차순 형태가 될것(<=)
        Stack<Integer> stack = new Stack<>();
        stack.add(0);
        int answer = 0;
        for (int i = 0; i < N; i++) {
            while (!stack.isEmpty() && stack.peek() > arr[i]) {
                stack.pop();
            }

            if (stack.isEmpty() || stack.peek() < arr[i]) answer++;

            stack.push(arr[i]);
        }

        System.out.println(answer);
    }
}

 

알고리즘 문제) BOJ 13146. 같은 수로 만들기 2

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

문제 요약

• n(1 ≤ n ≤ 1,000,000)개의 자연수 A[1], A[2], A[3], …, A[n]이 있다
• 자연수에 Add(i)라는 연산을 하면, A[i]가 1만큼 증가
  • 이때, A[i]의 좌우로 인접한 같은 수의 그룹도 한번에 1씩 증가
• 이와 같이 Add라는 연산을 사용하여 A[1] = A[2] = A[3] = … = A[n]이 되도록 하려 한다
• 최소 회수로 Add연산을 사용하는 방법을 찾아라

시간 제한

• 2초

입력

• 첫째 줄에 정수 n
• 다음 n개의 줄에는 차례로 A[1], A[2], …, A[n]
  • 든 입력은 1,000,000,000을 넘지 않는다

출력

• 첫째 줄에 최소의 Add연산 사용 회수를 출력
  • 값은 10^25를 넘지 않음

코드

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

        int N = Integer.parseInt(br.readLine());
        int num = Integer.parseInt(br.readLine()), max = num, prv = num;
        long answer = 0;
        for (int i = 1; i < N; i++) {
            num = Integer.parseInt(br.readLine());
            if (prv < num) {
                if (max < num) answer += num - max;
            } else {
                answer += prv - num;
            }
            prv = num;
            max = Math.max(num, max);
        }

        System.out.println(answer);

    }
}