1439번 : 뒤집기

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

1439번: 뒤집기

 

 

문제

 

 

코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.nextLine();
		int n=0;
		
		for(int i=0;i<s.length()-1;i++) {
			if(s.charAt(i) != s.charAt(i+1))
				n++;
		}
		
		if(n%2==0) n/=2;
		else n=(n/2)+1;
		System.out.print(n);
	}
}

 

 

해결방법

메모장에 몇 가지 문자열을 만들어서 규칙을 생각해본다면 한 문자열에서 0=>1, 1=>0 으로 바뀐 개수가 짝수개인 경우 n/2, 바뀐 개수가 홀수개인 경우 (n/2)+1한 값이 행동의 최소 횟수가 된다.

 

1111 => n=0 => 최소 횟수= 0/2 = 0
10 => n=1 => 최소 횟수= (1/2)+1 = 1
1010 => n=3 => 최소 횟수= (3/2)+1 = 2
110011 => n=2 => 최소 횟수= 2/2 =1
10101010 => n=7 => 최소 횟수= (7/2)+1 = 4
101010101 => n=8 => 최소 횟수= 8/2 = 4