1802_종이 접기 ***

사용 알고리즘: 애드 혹, 분할 정복이라고 한다.. (dfs를 곁들인)

사용 언어: java

 

 

대충 종이를 접어보면 → 가운데를 기준으로 양쪽이 대칭을 이루어야 함. 즉 0-1이든가 1-0이어야 함. 이거 이용해서 dfs로 풀었음

하지만 50퍼에서 틀린 코드

package week21;

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int test = Integer.parseInt(br.readLine());
		
		for(int t=0; t<test; t++) {
			String s = br.readLine();

			// 루트 -> 서브트리 루트...
			//루트 기준으로 양쪽이 01이거나 10이어야 함. 즉, 서로 다른 숫자여야 함
			
			int rootIdx = s.length()/2; //7/2=  3;
			boolean make = dfs_종이(s, rootIdx);
			
			if(make) System.out.println("YES");
			else System.out.println("NO");
		}
		
	}
	
	private static boolean dfs_종이(String s, int rootIdx) {
//		if(s.length() % 2 == 0) 
//			return false;
		if(s.length() == 1)
			return true;
		
		String left = s.substring(0, rootIdx); //100 맨끝
		String rigth = s.substring(rootIdx+1); //110 /맨앞
		
// 여기서 이제... left의 맨 끝과, right의 맨 앞만 비교 했따...
//그랬더니 50%에서 틀렸다.
// 그런데 생각해보니 left의 전체가 right의 전체의 반대가 되엉 ㅑ한ㄷ...
		
		return dfs_종이(left, left.length() /2) && dfs_종이(rigth, rigth.length() / 2);
	}

}

 

 

틀린 코드에서 좀만 더 생각했으면 됐는데….

답 코드

package week21;

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int test = Integer.parseInt(br.readLine());
		
		for(int t=0; t<test; t++) {
			String s = br.readLine();

			// 루트 -> 서브트리 루트...
			//루트 기준으로 양쪽이 01이거나 10이어야 함. 즉, 서로 다른 숫자여야 함
			
			int rootIdx = s.length()/2; //7/2=  3;
			boolean make = dfs_종이(s, rootIdx);
			
			if(make) System.out.println("YES");
			else System.out.println("NO");
		}
		
	}
	
	private static boolean dfs_종이(String s, int rootIdx) {
//		if(s.length() % 2 == 0) 
//			return false;
		if(s.length() == 1)
			return true;
		
		String left = s.substring(0, rootIdx); //100 맨끝
		String rigth = s.substring(rootIdx+1); //110 /맨앞
		
		
//		int rightIdx = left.length()-1 - i;
		for(int i=0; i<left.length(); i++) {
			int l = left.charAt(i) -'0';
			int r = rigth.charAt(left.length()-1 -i) - '0';
			
			if(l-r == 0)
				return false;
		}
		
		
		return dfs_종이(left, left.length() /2) && dfs_종이(rigth, rigth.length() / 2);
	}

}