[백준/BOJ] 17359. 전구 길만 걷자 [Silver 2]

17359. 전구 길만 걷자

문제출처 : https://www.acmicpc.net/problem/17359

#include <iostream>
#include <string.h>
#include <cstdlib>
using namespace std;

int main()
{
    char str[10][100] = { 0 };
    int N, cnt = 0, len, zto = 0, otz = 0, ztz = 0, oto = 0;

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> str[i];
        len = strlen(str[i]);
        for (int j = 0; j < len - 1; j++)
        {
            if (str[i][j] != str[i][j + 1])
                cnt++;
        }
        if (str[i][0] == '0' && str[i][len - 1] == '1')
            zto++;
        if (str[i][0] == '1' && str[i][len - 1] == '0')
            otz++;
        if (str[i][0] == '0' && str[i][len - 1] == '0')
            ztz++;
        if (str[i][0] == '1' && str[i][len - 1] == '1')
            oto++;
    }

    int add = abs(zto - otz);

    if (add > 1)
        cnt += (add - 1);

    if (zto == 0 && otz == 0 && ztz > 0 && oto > 0)
        cnt++;

    cout << cnt;

    return 0;
}

다소 무식한 방법을 썻지만, 코드짜는 방식이 서툴러서 그렇지 알고리즘은 맞다고 생각한다.

문자열배열을 입력받은대로 이어붙일생각을 하는게 아니라, 기본적으로 숫자가 바뀌는 횟수를 센 다음, 각 문자열의 양 끝 즉, 00인 경우 01인 경우 10인 경우 11인 경우를 각각 따져서 이어붙일때 추가되는 횟수를 세주었다.

규칙은 다음과 같다.

1) 01(10)이 10(01)보다 1개 이상 작은 경우

01(10)이 10(01)보다 1개 이상 작은 경우 추가 되는 횟수는 count-1회가 된다.

ex)

5

10

10

10

01

01

이면 추가되는 횟수는 0회이다. -> 1001100110으로 붙이면 되기때문이다.

but

7

10

10

01

01

01

01

01

이면 추가되는 횟수는 2회이다. -> 0110011001 01 01로 붙이기 때문이다.

2) 01또는 10가 모두0개이고, 00과 11가 1개이상있을때

01,10이 한개도 없다는 가정하에 00과 11가 1개이상있으면 개수에 상관없이 1개가 추가된다.

ex)

7

00

00

00

11

00

00

11

이면 0000000000 1111이런식으로 붙이면 되기 때문이다.