오늘의 알고리즘 - 그리디, 누적합, 투포인터

1. 그리디

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

public static class BOJ1439{
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String s = sc.nextLine();

            char counter = s.charAt(0); // 맨 처음 놈으로 시작

            int count = 1;

            for (char c : s.toCharArray()) {
                if (c != counter){
                    counter = c;
                    count++;
                }
            }

            System.out.println(count / 2);
        }
    }

• counter 를 판별하는 녀석으로. (바뀐 횟수 + 1) / 2 가 답이된다
• 10110 을 예로 들면, 1-> 0 한번, 0->1 두번, 1->0 세번 돌게 되는데
• 이 경우 4 / 2 = 2 가 답이됨.
• 마찬가지로 101101 은 4번 돌게 되는데, 이 경우 5 / 2 = 2 가 답이 된다. (따라서 count는 1로 시작해야 함)

---

2. 그리디 - 2217

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

    public static class BOJ2217 {
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int N = Integer.parseInt(br.readLine()); // 로프의 개수

            int[] arr = new int[N];

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

            Arrays.sort(arr);

            int max = Integer.MIN_VALUE;

            // 예를 들어 8, 10, 15 라면?
            for (int i = 0; i < N; i++) {
                max = Math.max(max, arr[i] * (N - i)); // 왜냐면 더 많은 중량을 버티는 로프들이 버텨주니까 N - i
            }

            System.out.println(max);
        }
    }

• 오름차순 정렬, 그리고 arr[i] * (N-i) 가 중요
• 예를 들어 0번 녀석은 젤 적게 드는 놈이므로, 이놈 제외 다른 모든 녀석들이 이 놈 도와줄 수 있음. 따라서 하중은 arr[0] * N 만큼 가능함

---

3. 누적 합 + 투포인터

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

    // 투포인터가 답인데?

    public static class BOJ2003 {
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());

            int N = Integer.parseInt(st.nextToken()); // 테스트케이스 개수
            int M = Integer.parseInt(st.nextToken()); // 누적합 목표

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

            st = new StringTokenizer(br.readLine());
            prefixSum[0] = 0;
            arr[0] = prefixSum[1] = Integer.parseInt(st.nextToken()); // 첫번째놈은 명시적으로 받아줌
            for (int i = 1; i < N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
                prefixSum[i + 1] = arr[i] + prefixSum[i];
            }

            int start = 0;
            int end = 1;

            int answer = 0;

            while (end < prefixSum.length){
                int sum = prefixSum[end] - prefixSum[start];

                ////1 3 5 9 11 16 19 20 21 23 < 누적합 배열
                // 1 2 3 4

                if (sum < M) { // 목표치보다 작다면, 오른쪽을 늘려야 하낟.
                    end++;
                } else if (sum > M){
                    start++;
                } else {
                    answer++; // 같을때는 증가시키고,
                    start++; // 시작도 하나 증가해줌.
                }
            }

            System.out.println(answer);
        }
    }

• 누적 구간 합

• 투포인터로 정리해주는 게 중요한데, 누적합 배열의 0번을 0으로 설정해야 한다.

• 왜냐면, 0번 인덱스 하나만으로도 M이 될 수 있기 때문