C# 1439 뒤집기

연속된 하나 이상의 숫자를 뒤집어서 모든 값을 통일한다

 

문자열 S={0001100}에서  S[0]==S[1]

                                          S[1]==S[2]

                                          S[2]!=S[3]

                                          S[3]==S[4]

                                          S[4]!=S[5]     

                                          S[5]==S[6]

S[0]부터S[2]의 값, S[5]부터 S[6]의 값이 0으로 같고, S[3]부터 S[4]의 값이 1로 같다

따라서 S[3]부터 S[4]의 값을 1번 뒤집는 것이 최소로 뒤집는 횟수이다

 

문제에서 나온 다른 예시들도 위의 과정처럼 하나씩 생각하다가

최소로 뒤집는 횟수의 규칙을 발견했는데

값이 다른 횟수/2를 올림한 것이 최소로 뒤집는 횟수이다

 

using System;
using System.Collections.Generic;
using System.Linq;

namespace _1439
{

    class Program
    {
        static void Main()
        {
            // 특정 수로 통일시키기 위해서, 0을 1로 바꾸거나 1을 0으로 바꿔야한다.
            // 연속된 하나 이상의 숫자를 모두 뒤집는 것이 가능하므로 
            // 연속된 숫자가 k개 있을 경우 k개를 한번에 뒤집는 것이 optimal solution이다.
            // 1이 연속되는 부분이 몇 개 있는지, 0이 연속되는 부분이 몇 개 있는지 확인한 다음 둘 중 가장 적은 것을 택하는 것이 답이 된다.

            var str = Console.ReadLine();
            var arr = Array.ConvertAll(str.ToArray().Select(x => x.ToString()).ToArray(), int.Parse);
            //int[] arr2 = new int[2];

            //여기부터 작성하세요 
            double difCount = 0;
            double flipCount = 0;

            for(int i = 0; i < str.Length-1; i++)
            {
                if (str[i] != str[i + 1])
                    difCount++;
            }
            flipCount = Math.Ceiling(difCount/2);
            Console.WriteLine(flipCount);
        }
    }
}

참고

https://yaraba.tistory.com/115

C# 반올림, 올림, 버림 사용하기

https://learn.microsoft.com/ko-kr/dotnet/api/system.math.ceiling?view=net-7.0 

Math.Ceiling 메서드 (System)

 

 

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

1439번: 뒤집기