(SWEA c++)4789. 성공적인 공연 기획

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

SW Expert Academy

 

모든 사람이 기립 박수를 하기 위해서는

i 번째에 도달했을 때의 박수를 친 사람의 합인지 확인을 해야한다.

 

예시처럼 110011 인 경우를 들어본다.

sum은 1 ~ s[i - 1]까지의 합이다.

0번째는 0이면 박수를 치지 않는 경우이기 때문에, 이를 제외하고는 sum에 값을 더한다.

 

그 다음부터는 1 ~ s[i]의 합이 해당 인덱스 이상인지 검사를 하면 된다.

1번째 인덱스 : 현재 박수 친 사람의 수는 0번째에서 1이기 때문에 sum = 1이 된 상태.

그러므로 sum += (1번째 인덱스의 수)1 을 한다.

 

2번째 인덱스 : 현재 sum = 2.

1 + s[1] = i.

인덱스와 합이 같으므로 sum += 0.

 

3번째 인덱스 : 현재 sum = 2.

1 + s[1] + s[2] = i.

2 = 3 이므로 사람이 부족한 상황이다.

그러므로 ans += i - sum을 해주어 부족한 사람의 수를 늘려주도록 한다.

그리고 sum = i + num을 해주어 사람을 채워놓도록 한다.

 

이런식으로 값을 구해나가면 된다.

문제 이해하는데 오랜 시간이 걸렸다...
글로도 잘 표현이 안되는 것 같두아...

 

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    
    for(int tc = 1; tc <= t; tc++)
    {
        string s;
        int sum = 0, ans = 0;
        
        cin >> s;
        
        for(int i = 0; i < s.size(); i++)
        {
            int num = s[i] - '0';
            
            if(num > 0)
            {
                if(sum >= i)
                    sum += num;
                else
                {
                    ans += (i - sum);
                    sum = i + num;
                }
            }
        }
        cout << "#" << tc << " " << ans << endl;
    }
    return 0;
}