[SWEA] 4789. 성공적인 공연 기획

문제

동욱이는 공연을 기획하고 있다. 이번이 그가 처음으로 기획한 공연이기 때문에, 성공에 매우 민감하여 반드시 공연을 성공시키겠다는 집념으로 불타고 있다.

동욱이는 이런 집착 중 하나로 공연이 끝난 후 모든 사람들의 기립 박수를 받고 싶다.

사람들은 공연이 끝난 후 모두 기립 박수를 할 생각이 있지만 기립 박수를 시작하는 타이밍은 사람마다 다를 수 있다.

이는 사람들이 가진 각자의 부끄러움 때문인데, 지금 기립 박수를 하고 있는 사람의 수가 특정한 수 이상이 되면 그제서야 일어나서 기립 박수를 하게 되는 것이다.

이 특정한 수를 넘지 않으면 절대로 기립 박수를 하지 않는다.

그렇기에 우선 아무런 조건이 없이 기립 박수를 하는 사람들이 기립 박수를 시작하고, 그것을 본 다른 사람들이 또 일어나서 연쇄적으로 기립 박수를 하게 된다.

그리고 조건을 만족하지 못한 사람들은 부끄러움에 계속해서 앉아있게 된다.

그래서 동욱이는 먼저 공연의 표를 예약한 사람들의 정보를 개개인에 대해 모두 조사하여, 각 사람들이 기립 박수를 하려면 최소 몇 명의 사람들이 기립 박수를 하고 있어야 하는지를 알게 되었다.

각 사람들의 조건이 모두 다르기 때문에, 구성이 어떤 지에 따라 몇몇의 사람은 기립 박수를 하지 않을 수도 있다.

그래서 몇 명의 사람들을 고용하여 공연이 끝난 후 기립 박수를 바로 하게 하여 실제로 표를 사서 공연을 관람한 사람들이 모두 기립 박수를 하도록 하게 하고 싶다.

최소 몇 명의 사람들을 따로 고용해야 할까?

 

풀이방법

i번째 사람들이 박수 치기 위해서는 1부터 i-1번째 사람들의 합이 i가되어야한다. 

 

s[i]를 1부터 i번째 사람들의 합이라고 하고, a[i]가 i번째 사람들이 박수 치기위해 필요한 인원이라한다면

 

a[i] = i - s[i-1]

 

의 식을 세워 구할 수 있다.

 

소스코드

package samsung;

import java.util.*;

public class s_4789 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int test = sc.nextInt();
		for(int t = 1; t <= test; t++) {
			String s = sc.next();
			int sum = 0;
			int cnt = 0;
			
			for(int i = 0; i < s.length(); i++) {
				int tmp = s.charAt(i) - '0';
				if(tmp > 0) {
					if(sum >= i) {
						sum += tmp;
					}
					else {
						cnt += (i - sum);
						sum = i + tmp;
					}
				}
			}
			System.out.println("#" + t + " " +cnt);
		}
	}
}

 

출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWS2dSgKA8MDFAVT&categoryId=AWS2dSgKA8MDFAVT&categoryType=CODE

SW Expert Academy