(java)BOJ 13413 오셀로 재배치

13413번: 오셀로 재배치

문제 풀이

난이도를 모르고 딱 처음에 봤을 때는 bfs가 떠올랐다. 근데 문제를 자세히 보면 입력 범위 자체도 bfs로 풀기는 말이 안되고 풀이 자체도 bfs로는 안될 것으로 판단됐다.

돌을 다른 것과 순서를 바꿔주는 것은 한 번에 두 개의 돌을 바꿔주기 때문에 그리디하게 최대한 많이 두 개의 돌의 순서를 바꿔주면 된다고 생각했다.

그리고 남는 돌들은 그냥 목적과 같은 색으로 바꿔주면 된다.

package solving;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Solution_13413_오셀로재배치 {

	public static void main(String[] args) throws Exception{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(in.readLine());
		for(int t_c = 0; t_c < t; t_c++) {
			int N = Integer.parseInt(in.readLine());
			String first = in.readLine();
			String purpose = in.readLine();
			int differentWhite = 0; // 목적과 다른데 흰색인 것
			int differentBlack = 0; // 목적과 다른데 흑색인 것
			
			for(int i = 0; i < N; i++) {
				if(first.charAt(i) != purpose.charAt(i)) {
					if(purpose.charAt(i) == 'W') {
						differentWhite ++;
					}
					else {
						differentBlack ++;
					}
				}
			}
			int answer = 0;
			if(differentBlack > differentWhite) {
				answer += (differentWhite + differentWhite) / 2; // 적은 것을 * 2 한 다음에 2로 나눈 몫을 취한다.
				answer += differentBlack - differentWhite; // 큰 것에 작은 것을 뺀 것을 취한다.
			}else {
				answer += (differentBlack + differentBlack) / 2;
				answer += differentWhite - differentBlack;
			}
			System.out.println(answer);
		}
	}
}