2회 문제풀이 14 / ABC 120 C - Unification
ABC 120 C - Unification
【문제 개요】
책상 위에 N개의 큐브가 세로로 쌓여 있습니다. 길이 N의 문자열 S가 주어집니다.
밑에서부터 i번째의 큐브의 색은 S의 i번째 문자가 0일경우 빨간색, 1이면 파란색이다.
당신은 빨간색 큐브와 파란색 큐브가 인접한 부분을 선택해 그 2개의 큐브를 제거하는 조작을 반복할생각입니다.
이렇게 큐브를 제거한다면 제거한 큐브 위에 있던 큐브는 그대로 아래로 떨어집니다. 이렇게 최대 몇개의 큐브를 제거할 수 있습니까?
힌트 : 깊이 우선 탐색(DFS) 알고리즘
【전제】
- 1 ≦ N ≦ 10^5
- S의 문자열 길이 = N
- S는
0과1로만 구성되어있다.
【입력 형태】
1
S
【출력 형태】
최대 몇개의 큐브를 제거할 수 있는지 출력하라.
【예시】
입력 예 1
1
0011
출력 예 1
1
4
다음의 순서로 조작하면 4개의 큐브를 모드 제거할 수 있습니다.
- 아래에서 2번째 큐브와 3번째 큐브를 제거합니다. 그 결과 4번째 큐브가 아래에서 1번째 큐브 위로 떨어집니다.
- 아래에서 1번째 큐브와 2번째 큐브를 제거합니다.
입력 예 2
1
11011010001011
출력 예 2
1
12
입력 예 3
1
0
출력 예 3
1
0
ABC 120 C - Unification
【문제 개요】
책상 위에 N개의 큐브가 세로로 쌓여 있습니다. 길이 N의 문자열 S가 주어집니다.
밑에서부터 i번째의 큐브의 색은 S의 i번째 문자가 0일경우 빨간색, 1이면 파란색이다.
당신은 빨간색 큐브와 파란색 큐브가 인접한 부분을 선택해 그 2개의 큐브를 제거하는 조작을 반복할생각입니다.
이렇게 큐브를 제거한다면 제거한 큐브 위에 있던 큐브는 그대로 아래로 떨어집니다. 이렇게 최대 몇개의 큐브를 제거할 수 있습니까?
힌트 : 깊이 우선 탐색(DFS) 알고리즘
【전제】
- 1 ≦ N ≦ 10^5
- S의 문자열 길이 = N
- S는
0과1로만 구성되어있다.
【입력 형태】
1
S
【출력 형태】
최대 몇개의 큐브를 제거할 수 있는지 출력하라.
【예시】
입력 예 1
1
0011
출력 예 1
1
4
다음의 순서로 조작하면 4개의 큐브를 모드 제거할 수 있습니다.
- 아래에서 2번째 큐브와 3번째 큐브를 제거합니다. 그 결과 4번째 큐브가 아래에서 1번째 큐브 위로 떨어집니다.
- 아래에서 1번째 큐브와 2번째 큐브를 제거합니다.
입력 예 2
1
11011010001011
출력 예 2
1
12
입력 예 3
1
0
출력 예 3
1
0
このポストは作成者の CC BY 4.0 ライセンスによって保護されます。