백준 13413 - 오셀로 재배치

백준 13413 - 오셀로 재배치

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

★ 풀이

주어진 목표에 도달하기 위해 2가지 방법을 적절히 사용하여 최소 횟수로 도달하는 방법을 찾는 문제이다.

원래 문자열에서 목표 문자열을 만들기 위해서는 기존의 문자열을 뒤집거나 문자열 안에서 스왑하는 방법을 사용할 수 있다. 이때 기존의 문자열과 목표 문자열이 다른 Point에는 2가지 종류가 존재한다.

WB 혹은 BW

간단한 예시를 먼저 들어 설명하겠다.

위에서 보여지듯 한쌍의 WB와 BW는 SWAP으로 1번에 해결할 수 있다.(뒤집기로는 2번 걸림)

그렇다면 결국 위에서 보여지듯이 PAIR(WB+BW)의 쌍의 개수 + 나머지의 값으로 최소값을 구할 수 있는 것이고

이 값은 아래 식과 같다.

case1은 WB, case2는 BW의 개수를 의미한다.

Math.max(case1, case2);

★ 소스 코드

import java.io.*; import java.util.*; // 좋은 코드 흡수하기! public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static int n; public static void main(String[] args) throws IOException { // 주어진 목표에 도달하는 최소 횟수 int T = Integer.parseInt(br.readLine()); while(T-->0) { n = Integer.parseInt(br.readLine()); String now = br.readLine(); String target = br.readLine(); bw.write(findMin(now, target)+"

"); } bw.flush(); } static int findMin(String now, String target) { int ret = 0; int case1 = 0; int case2 = 0; for(int i = 0; i

from http://sweet-smell.tistory.com/121 by ccl(A) rewrite - 2021-11-29 15:02:01