반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. 규칙


우선 예제 입력을 0으로 만드는 법이라고 생각을 하고 문제를 풀어보자.


이 문제를 풀기 위해서는 1이 언제 0이되는지 생각해볼 수 있다.

1을 0으로 만들기 위해 1의 좌, 우, 현재 위치를 누르면 해당 위치의 1은 없어진다.


이를 통해 가장 앞에있는 1부터 하나씩 없애주면 되는데

해당하는 1의 위치 오른쪽을 누름으로써 1을 하나씩 차근차근 없애면 문제를 해결 할 수 있다.







소스 코드 : 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
int arr[1000012];
 
int main() {
    int n;
    cin >> n;
 
    int cnt = 0;
    for (int i = 0; i < n; i++)
        scanf("%d"&arr[i]);
 
    for (int i = 0; i < n; i++)
    {
        if (arr[i])
        {
            arr[i] = !arr[i], arr[i + 1= !arr[i + 1], arr[i + 2= !arr[i + 2];
            cnt++;
        }
    }
    return !printf("%d", cnt);
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[1708번] 볼록 껍질  (0) 2018.06.27
[13326번] Diameter  (0) 2018.06.21
[1933번] 스카이라인  (2) 2018.05.11
[14915번] 진수 변환기  (0) 2018.05.08
[14911번] 궁합 쌍 찾기  (0) 2018.05.07