[코드트리] G&H 반전시키기3 C++

문제

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

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 쪼개기

주어지는 것

문자열의 개수 n

초기 문자열

목표 문자열

목표

구간을 최소 횟수로 잡아 해당 구간에 있는 문자를 ‘G’ → ‘H’, ‘H’ → 'G’로 반전시켜 원하는 목표 문자열이 나오도록 하는 프로그램을 작성

조건

한번에 뒤집을 수 있는 구간의 최대 크기 4

 

문제가 살짝 이해하기 어려웠다(최소 구간의 수라는 게 구간의 크기인지 구간이 몇 덩어리로 나누어지는 것인지 헷갈렸음)아래 예제의 경우 [0,4]구간을 뒤집어야 한다.7GHHHGHHHGGGHHH한 번에 4개까지 뒤집을 수 있으므로, 뒤집을 수 있는 경우는 아래와 같다0, 1, 2, 3, 4 => 5번 뒤집기...(생략)0, [1,4] => 2번 뒤집기[0,1], [2,4] => 2번 뒤집기[0,2], [3,4] => 2번 뒤집기[0,3], 4 => 2번 뒤집기1번에 뒤집을 수는 없으므로 답은 2가되는 것.

 

코드

#include <iostream>
using namespace std;

int n;
string initStr, targetStr;

int main() {
    cin >> n;
    cin >> initStr >> targetStr;
    int range=0, numOfSection=0;
    for(int i=0; i<n; ){
        if(initStr[i]!=targetStr[i]){
            while(i<n && initStr[i]!=targetStr[i]){
                i++;
                range++;
            }

            if(range%4==0) numOfSection+= range/4;
            else numOfSection+= range/4+1;
        }
        range=0;
        i++;
    }

    cout << numOfSection << '\n';
    return 0;
}