[BOJ] 31005 - 귤나무

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

BOJ - 귤나무

문제 유형: 애드 혹, 수학

문제 난이도: Gold I

시간 제한: 1초

메모리 제한: 1024MB

 

문제

서윤이네 뒷마당에는 M개의 귤이 열려 있는 커다란 귤나무가 있다.

이웃집에 사는 N마리의 곰곰이들은 이 귤나무에 매일 귤을 따러 온다. 매일 1번 곰곰이부터 시작해서 N번 곰곰이까지 차례대로 귤을 따려고 시도하는데, i번 곰곰이는 A_i개의 귤을 따려고 시도하며 나무에 남은 귤이 A_i개 미만이라면 아무 행동도 하지 않는다.

 10^{100} 일이 지났을 때, 귤나무에 남아있는 귤의 개수는 몇 개일지 구해보자.

 

입력

첫째 줄에 곰곰이의 수와 귤의 개수 N, M이 공백으로 구분되어 주어진다. 1 <= N <= 200,000; 1 <= M <= 10^{18}

둘째 줄에 각 곰곰이가 따갈 귤의 개수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 1 < =A_i <= 10^{12}

입력으로 주어지는 모든 수는 정수이다.

 

출력

10^{100} 일이 지났을 때 귤나무에 남아있는 귤의 개수를 출력한다.

 

풀이

사실, 10^100일이라는 시간은 의미없다. 

10^18일동안 1마리의 곰곰이가 1개씩만 가져가도 10^100에는 훨씬 못미친다.

그러나, 역시 10^18이라는 날짜를 시뮬레이션 하는 것은 무리이다. 10^8 ~ 10^9 정도가 알고리즘 문제 풀이에서의 적정 연산량이다.

 

어떻게 가져가는 시간을 최소화 할 수 있을까?

정답은 "반복되는 가져가기 루틴을 불가능하기 전까지 반복"이다.

그리고, "한 번 못 가져가기 시작한 곰곰이는 다시는 가져갈 수 없다"라는 사실 역시 중요하다.

 

curr 배열에는 현재 귤나무에서 가져갈 수 있는 곰곰이들의 a값들을 저장한다.

아래 반복을 계속한다:

1. 이들의 합인 sum을 구해서, m %= sum연산을 취한다. sum만큼 가져가는 나날들이 반복될 것이기 때문이다.
2. 그 뒤, 순차적으로 curr을 돌면서, a값이 m보다 작거나 같아서 귤을 가져갈 수 있는 경우에만 m -= a를 취하고, next배열에 넣는다.
3. next배열이 비어있다면, 이 반복을 멈춘다.
4. 다음 curr은 next이다.

최종적으로 남은 m을 구해주면 된다.

 

시간 복잡도는 amortized O(n)이다.

 

 

코드

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

var reader *bufio.Reader
var writer *bufio.Writer

func main() {
	reader = bufio.NewReader(os.Stdin)
	writer = bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n, m int64
	fmt.Fscan(reader, &n, &m)

	curr := make([]int64, n)
	for i := int64(0); i < n; i++ {
		fmt.Fscan(reader, &curr[i])
	}

	for {
		sum := int64(0)
		for i := 0; i < len(curr); i++ {
			sum += curr[i]
		}

		m = m % sum

		next := make([]int64, 0)
		for _, a := range curr {
			if a <= m {
				m -= a
				next = append(next, a)
			}
		}

		if len(next) == 0 {
			break
		}

		curr = next
	}

	fmt.Fprintln(writer, m)

}