swea 2105 <디저트 카페>

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu&categoryId=AV5VwAr6APYDFAWu&categoryType=CODE

SW Expert Academy

이전에 풀었던 게리맨더링 2오 비슷한 문제이다 이문제를 풀어보게 된다면 이 문제도 같이 풀어보는 것이 좋다.

 

skygood95.tistory.com/25

백준 17779 <게리멘더링2>

위의 게리맨더링 2에서 푼 방법과는 조금 다르게 문제를 해결했다.

 

문제의 해결방법은 가난하게 총 2가지이다.

1.  시작점 X,Y 좌표를 선택하고 오른쪽 아래 대각선 길이 re , 왼쪽 아래 대각선 le 값을 4중 for문으로 정한다.
2. 4개의 꼭지점 범위가 map안에 해당하면 탐색을 실시한다.
   1. 시작점에서 오른쪽 하단으로 re 만큼 가면서 검사,
   2. 두 번째 지점에서 왼쪽 하단으로 le 만큼 가면서 검사
   3. 세 번째 지점에서 왼쪽 상단으로 re 만큼 가면서 검사
   4. 마지막 점에서 오른쪽 상단으로 가면서 검사

이렇게 수행하게 되면 총 걸리는 시간은 최대 X, Y, re, le를 선택하는데 20*20*20*20 해서 160000 16만 검사를 하는데 걸리는 시간은 최대 20*4 이므로 12800000으로 간단하게 끝낼 수 있다.

 

위의 i, j는 시작점을 찾는 것이고 re는 우 하단 대각선 길이, le는 좌 하단 대각선 길이이다. 

이 그림처럼 최대 이동 할수 있는 범위를 벗어나면 해당할 수 없으니 제외를 시켜준다!

 

 

시작점으로 부터 1-->2-->3 순서대로 가면서 같은 디저트를 먹게 된다면 return을 해주고 아니라면 count 값과 총 합 중 최댓값을 저장한다.

 

이렇게 순서 대로 진행하는 방법이 있다.

 

또한 다른 방법이 있다고 하면 le+re의 총합은 한 변의 길이보다 1이 작기 때문에 이 부분을 고려해서 크기 큰 것에서부터 해서 비교를 해 줄 수 있을 것 같다!

 

 이렇게 n이 4인 경우에 총 만들수 있는 le+re 는 n-1 즉 3이므로 이를 이용해서 계산할 수 있다고 한다! 참고!!

 

전체 코드

 

package z;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class start {

	static int map[][],t,n,dir[][]= {{1,1},{1,-1},{-1,-1},{-1,1}},count=-1;
	static boolean visit[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		t=Integer.parseInt(br.readLine());
		for(int tc=1;tc<=t;tc++) {
			n=Integer.parseInt(br.readLine());
			map=new int[n][n];
			count=0;
			for(int i=0;i<n;i++) {
				StringTokenizer st=new StringTokenizer(br.readLine());
				for(int j=0;j<n;j++) {
					map[i][j]=Integer.parseInt(st.nextToken());
				}
			}
			for(int i=0;i<n-2;i++) {
				for(int j=1;j<n-1;j++) {
					ll:for(int le=1;le<n;le++) {
						for(int re=1;re<n;re++) {
							int rx=i+dir[0][0]*le;
							int ry=j+dir[0][1]*le;
							if(rx>=n||ry>=n) {
								break ll;
							}
							int lx=rx+dir[1][0]*re;
							int ly=ry+dir[1][1]*re;
							if(lx>=n||ly<0) {
								break;
							}
							int lastx=lx+dir[2][0]*le;
							int lasty=ly+dir[2][1]*le;
							if(lastx<0||lasty<0)
								break;
							find(i,j,le,re);
						}
					}
				}
			}
			System.out.println("#"+tc+" "+count);
		}
		
	}
	private static void find(int x, int y, int le, int re) {
		// TODO Auto-generated method stub
		visit=new boolean[101];
		visit[map[x][y]]=true;
		for(int i=0;i<le;i++) {
			x+=dir[0][0];
			y+=dir[0][1];
			if(visit[map[x][y]])
				return;
			visit[map[x][y]]=true;
		}
		for(int i=0;i<re;i++) {
			x+=dir[1][0];
			y+=dir[1][1];
			if(visit[map[x][y]])
				return;
			visit[map[x][y]]=true;
		}
		for(int i=0;i<le;i++) {
			x+=dir[2][0];
			y+=dir[2][1];
			if(visit[map[x][y]])
				return;
			visit[map[x][y]]=true;
		}
		for(int i=0;i<re-1;i++) {
			x+=dir[3][0];
			y+=dir[3][1];
			if(visit[map[x][y]])
				return;
			visit[map[x][y]]=true;
		}
		count=Math.max(re*2+le*2,count);
		
	}
}