G1720. 타일코드

문제

제출 코드

• 사용 알고리즘 : DP

DP라고 만만하게 보고 건드렸다가 큰 코 다쳤다. 전날 스터디에서 풀 문제를 고르면서 나왔는데, 이전에 풀었던 타일링 문제 1, 2랑 비슷해보이길래 빨리 끝날 줄 알고 풀기 시작했는데, 생각보다 접근법이 까다로워서 이틀에 걸쳐 풀게 되었다.

이 문제의 핵심은 양쪽이 대칭인 파일을 어떻게 찾아내느냐인데, 주어진 N이 짝수와 홀수중 어느것인지에 따라 계산법이 달라져서 그 부분을 관리하는 과정중에 헷갈렸다.

처음엔 마지막에만 대칭 관리를 하면 되겠지 하고(이게 맞다), 이전에 알고리즘 응용 수업중에 들은 더 최적화된 타일링 풀이법을 적용해서 풀어보고자 했다.

홀수인 경우는 기존과 같이 구하지만, 짝수의 경우엔 반절까지만 dp값을 알아도 계산 가능해서, 기존의 시간복잡도 O(N)에서 O(logN)까지 줄일 수 있다는 것이다.

근데 기존 dp도 O(N)이어서 아무리 N이 커도 어느 문제를 풀던간에 크게 문제가 없긴 하다.

결과적으로 저 방식을 구현하면서 대칭까지 생각하는 와중에 코드가 꼬여서 과감히 포기했다.

모든 타일의 경우의 수는 양쪽이 대칭인 경우와, 그렇지 않은 경우로 나뉜다.

문제에서는 양쪽이 대칭인 경우는 같은 타일로 구분한다 했으니, 대칭인 경우를 찾아서 구해둔 dp값에서 빼주면 문제는 해결된다.

그러나 대칭인 타일은 또다시 원래 대칭인 경우(양쪽 타일 모양 같음), 뒤집어서 대칭이 되는 경우(양쪽 타일 모양은 다름) 으로 나뉘는데, 우리는 후자의 경우만 전체 dp에서 빼줘야 한다.

그러나 후자의 경우를 찾는것은 전자를 찾는것보다 더 어렵기에, 전체 dp에 전자인 경우의 수를 더해준다음 2로 나눠주는 방식을 선택했다.

양쪽 타일이 모두 같은 경우(전자)는 N이 홀수인지 짝수인지에 따라 아래와 같이 나뉜다.

N까지 dp를 모두 구해준 후, N의 값에 따라 위의 식을 계산하면 정답이다.

package gold;

import java.util.Scanner;

public class G1720_tileCode {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		int[] dp = new int[N+1];
		dp[1] = 1;
		if(N>1) dp[2] = 3;
		if(N<3) {
			System.out.println(dp[N]);
			return;
		}
		for(int i=3; i<=N; i++) dp[i] = dp[i-1] + 2*dp[i-2];

		int re;
		if(N%2==0) re = dp[N/2] + 2*dp[N/2-1];
		else re = dp[(N-1)/2];

		System.out.println((dp[N]+re)/2);
	}

}