[백준] 23322 - 초콜릿 뺏어 먹기

1. 문제

23322번: 초콜릿 뺏어 먹기

2. 개요

초콜릿이 담긴 N개의 병들이 오름차순으로 정렬되어있다.

이 병에서 하루에 한 번 다음과 같은 전략으로 초콜릿을 먹는다.

1. K < i인 i를 골라, i-K번째 통에 있는 초콜릿의 개수와 똑같아질 때까지 i번째 통에서 초콜릿을 꺼내 먹는다.
2. 그 후 통을 재정렬한다. 즉, 초콜릿의 개수가 오름차순이 되도록 통을 재배치 한다.

최대한 빨리, 최대한 많은 초콜릿을 먹으려고 할 때 걸리는 일 수와 먹을 수 있는 초콜릿의 개수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

2번 조건에 의해 최소값은 결국 1번 병이 되고, 1번 조건에 의해 모든 병은 결국 1번 병과 같은 값을 가지게 된다.

따라서 모든 병을 1번 병과 같은 값으로 만들 때의 값을 구하면 된다.

3-2. Python

import sys

N, K = map(int, sys.stdin.readline().split())

chocos = list(map(int, sys.stdin.readline().split()))

days, ate = 0, 0

for i in range(1, N):
    if chocos[i] != chocos[i-1]:
        ate += chocos[i] - chocos[i-1]
        days += 1
        chocos[i] = chocos[i-1]

print(ate, days)

3-3. C#

namespace boj_23322
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();

            int N = int.Parse(input[0]);
            int K = int.Parse(input[1]);

            int days = 0;
            int ate = 0;

            int[] chocos = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);

            for (int i = 1; i < N; i++)
            {
                if (chocos[i] != chocos[i - 1])
                {
                    ate += chocos[i] - chocos[i - 1];
                    days++;
                    chocos[i] = chocos[i - 1];
                }
            }

            sw.WriteLine($"{ate} {days}");
            sw.Close();
        }
    }
}