코드트리 조별과제 6회차 (8.19 ~ 8.25)

상태 반전이 가능한 문제

 

[ 문제 ]

문자열 길이 4인 0100이 주어졌을 때, 부분 문자열을 고르면, 해당 문자열 내 문자들이 0은 1, 1은 0으로 반전이 일어난다고 한다. 이때, 부분 문자열을 적절하게 골라 최소 횟수로 문자열이 1111이 되도록 하세요.

 

 

[ 접근 방법 ]

0100에서 [2,2] 구간을 0000으로 만든 뒤, [1,4] 구간을 뒤집으면 1111이 되므로 최소 횟수는 2가 된다.

먼저, 다음과 같이 생각을 해보자. 전부 숫자 1을 만들기 위해 뒤집어야 하는 구간 끼리는 어떤 관계가 있을까? 문제 특성상, 두 구간이 겹치는 곳에 있는 문자들은 2번 뒤집히기 때문에 결국 뒤집히지 않은 것과 같다.

즉, 2번 뒤집혔다는 것은, 뒤집지 않았다는 것과 같다. 이는 곧, 뒤집을 필요가 없다는 말과도 같다.

예를 들어, 0011100이 주어졌을 때, 111을 뒤집는 구간과 뒤집은 뒤 모두 1로 뒤집는 구간 이 나올 것이다. 그러나, 111을 두 번 뒤집기 때문에 양쪽 00만 뒤집기하는 것과 같다.

 

그러므로. 겹치는 두 구간은 항상 겹치지 않게 할 수 있으며, 어떤 최적의 방법이 있을 때 겹치는 두 구간을 푸는 방식을 반복하여 모든 구간이 겹치지 않으며 뒤집는 구간의 수는 동일한 경우로 만들 수 있다는 것이다.

이처럼 구간 단위로 뒤집는 문제의 경우, 구간을 겹쳐서 해결할 필요가 없음 을 이해한다면, 간단히 해결 가능합니다.

 

 

 

연습문제 - (코드트리) G ＆ H 반전시키기

 

 

https://www.codetree.ai/missions/8/problems/reversing-g-and-h?&utm_source=clipboard&utm_medium=text

 

 

import java.util.*;
import java.io.*;

public class Main {
    static int N, ans;
    static String init, target;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        init = br.readLine();
        target = br.readLine();

        solve();

        System.out.println(ans);
    }

    static void solve(){
        boolean inSegment = false;

        for(int i=0; i<N; i++){
            if(init.charAt(i) != target.charAt(i)){
                if(!inSegment){
                    ans++;
                    inSegment = true;
                }
            }
            else{
                inSegment = false;
            }
        }
    }
}