고양멍멍이

[문제링크]

0. 메모리제이션을 이용해 동일 지점에 대한 중복연산을 피한다

  - 1-2-3-4-5 루트와 6-7-3-4-5 루트는 3-4-5가 겹치니 연산 결과를 저장, 결과가 존재하지 않을때만 사용 

1. 주변에 진행할 방향이 없어도 1만큼은 살 수 있으므로, cache배열은 초깃값 0을 유지

2. 아직 거쳐가지 않은 장소마다 rec함수로 살 수 있는 최대 년수를 확인한다

  - 검사한 모든 경로의 cache에 결과값을 저장함으로서, 재방문시 즉시 반환되도록 한다

3. 이미 cache가 존재하는 장소의 경우, 다른 경로의 중간 경로로서 저장된 것

  - 즉, 더 긴 결과값의 일부로서 사용됬기 때문에 무시한다

  - (사실 진입해도 즉시 반환되므로 성능상 별 영향은 없다)

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

public class Main{
	static int[][]map;
	static int[][]cache;
	static int max=0;
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		int N = pint(br.readLine());
		map=new int[N+2][N+2];
		cache=new int[N+2][N+2];
		
		for (int i = 0; i < N+2; i++) {
			map[i][0]=-1;map[i][N+1]=-1;
			map[0][i]=-1;map[N+1][i]=-1;
		}
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i+1][j+1]=pint(st.nextToken());
			}
		}

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if(cache[i][j]==0) {
					max=Math.max(max, rec(i,j));
				}
			}
		}
		System.out.println(max);
	}
	
	static int rec(int x, int y) {
		if(cache[x][y]!=0)return cache[x][y];
		
		int temp=0;
		
		if(map[x][y]<map[x+1][y])temp=Math.max(temp, rec(x+1,y));
		if(map[x][y]<map[x][y+1])temp=Math.max(temp, rec(x,y+1));
		if(map[x][y]<map[x-1][y])temp=Math.max(temp, rec(x-1,y));
		if(map[x][y]<map[x][y-1])temp=Math.max(temp, rec(x,y-1));
		
		cache[x][y]=1+temp;
		return cache[x][y];
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. x,y지점에서 총 m칸, 최대 무게 c를 고려해 채취할 수 있는 꿀의 최대 가치는 항상 동일하다

  - 미리 연산해서 저장 후 활용한다

1. 위에서 구한 가치들 중, 구간이 겹치지 않으면서 가치의 합이 최대가 되는 두 구역을 찾는다

2. 가치가 큰 순서로 정렬한다

  - 최대 가치 구간을 한 구간으로 잡고 그리디하게 계산한 최댓값이 최댓값이 아니려면

  - 최대 가치 구간과 영역이 겹치는 다른 구간에서 나온 값만이 가능하다

3. 영역이 겹치는 구간의 수는 2*m-1개로, 정렬된 구간을 그만큼만 살펴보면

  - 그리디하게 구한 결과의 가능한 모든 반례를 고려한 결과가 나온다

* 최대 가치를 가지는 영역 X와, 이에 속하지 않는 영역중 최대 가치를 가진 Y의 합 : 그리디한 해결법 으로 생각하면

  - X+Y의 가치보다 큰 값은 X와 영역이 일부 겹치는 X'들이 서로 합쳐졌을때만 가능하다

  - m이 3이라면, n이 충분할 때 겹치는 영역은 최대 5개(자기 자신 포함) 

  - 1위가 최대영역 X이고, 2,3,4,5위가 X와 영역을 공유할 때 그리디한 답은 1위 + 6위

  - 2,3,4,5위의 해답만이 1+6위의 결과를 넘을 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Solution{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			n = pint(st.nextToken());
			m = pint(st.nextToken());
			c = pint(st.nextToken());
			map = new int[n][n];
			for (int i = 0; i < n; i++) {
				st=new StringTokenizer(br.readLine());
				for (int j = 0; j < n; j++) {
					map[i][j]=pint(st.nextToken());
				}
			}
			collect = new ArrayList<>();
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n-m+1; j++) {
					int temp =calMax(i,j,0,0,0); 
					collect.add(new int[] {i, j, temp});
				}
			}
			
			Collections.sort(collect, new Comparator<int[]>() {
				@Override
				public int compare(int[] o1, int[] o2) {
					return o2[2]-o1[2];
				}
			});
			
			int max=0, len = Math.min(m*2-1, n-m+1);
			for (int i = 0; i < len; i++) {
				int[] fst = collect.get(i);
				for (int j = i+1; j < collect.size(); j++) {
					int[] snd = collect.get(j);
					if(fst[0]==snd[0] && Math.abs(fst[1]-snd[1])<m)continue;
					
					if(max<fst[2]+snd[2]) {
						max=fst[2]+snd[2]; break;
					}
				}
			}
			sb.append("#").append(testcase).append(" ").append(max).append("\n");
		}System.out.println(sb);
	}
    
	static int n,m,c;
	static int[][]map;
	static ArrayList<int[]>collect;
    
	static int calMax(int i,int j, int cost, int wid, int cnt) {
		if(wid>c)return 0;
		if(cnt==m) {
			return cost;
		}
		int temp=0;
		temp = calMax(i,j+1, cost+map[i][j]*map[i][j], wid + map[i][j], cnt+1);
		temp = Math.max(temp, calMax(i,j+1, cost, wid, cnt+1));
		return temp;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 벨만-포드 알고리즘

1. 시작노드로부터, 모든 도로에 대해 n-1번 갱신하면 각 노드까지의 최소 거리

2. 한번 더 돌렸을때 변동되는 값이 존재한다면 음수 cycle이 존재하기 때문

3. 도달할 수 없는 노드도 갱신하도록 해 시작노드와 연결되지 않아도 음수 사이클은 탐지 가능

* 현재 코드는 a->b가 갱신됬을 때, 같은 단계에서 갱신된 b로 인해 b->c의 결과도 변할 수 있는 코드

  - 음수 사이클이 있다면 n번째 단계의 결과값은 이미 사이클을 몇번 돈 결과일 수 있다

  - 하지만 음수 사이클을 탐지할 땐 상관 없음

개선점 : 두 지점 사이에 여러 도로가 있을 수 있으므로, 입력단계에서 처리해 성능 향상 가능

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = pint(st.nextToken());
			int m = pint(st.nextToken());
			int w = pint(st.nextToken());
			ArrayList<ArrayList<int[]>>graph2=new ArrayList<>();
			for (int i = 0; i <= n; i++) {
				graph2.add(new ArrayList<>());
			}
			//도로 입력
			for (int i = 0; i < m; i++) {
				st = new StringTokenizer(br.readLine()," ");
				int n1 = pint(st.nextToken()), n2 = pint(st.nextToken());
				int cost = pint(st.nextToken());
				graph2.get(n1).add(new int[] {n2,cost});
				graph2.get(n2).add(new int[] {n1,cost});
			}
			//웜홀입력
			for (int i = 0; i < w; i++) {
				st = new StringTokenizer(br.readLine()," ");
				int n1 = pint(st.nextToken()), n2 = pint(st.nextToken());
				int cost = pint(st.nextToken())*-1;
				graph2.get(n1).add(new int[] {n2,cost});
			}
			int[] dist=new int[n+1];
			int[] dist2=new int[n+1];
			Arrays.fill(dist, 6000000);//이론상 최댓값 : 4990000
			dist[1]=0;//시작노드 1
			
			for (int i = 0; i < n-1; i++) {
				
				for (int j = 1; j <= n; j++) {
					for (int j2 = 0; j2 < graph2.get(j).size(); j2++) {
						int[] cur = graph2.get(j).get(j2);
						dist[cur[0]]=Math.min(dist[cur[0]], dist[j]+cur[1]);
					}
				}
				
			}//n-1번 실행
			
			//1번 더 실행
			dist2 = dist.clone();

			for (int j = 1; j <= n; j++) {
				for (int j2 = 0; j2 < graph2.get(j).size(); j2++) {
					int[] cur = graph2.get(j).get(j2);
					dist2[cur[0]]=Math.min(dist2[cur[0]], dist2[j]+cur[1]);
				}
			}
			//결과값이 달라진게 있다면 : 음수 cycle이 존재한다
			String ans = "NO";
			for (int i = 1; i <= n; i++) {
				if(dist[i]!=dist2[i]) {
					ans="YES";
					break;
				}
			}
			
			sb.append(ans).append("\n");
		}//end of tc
		System.out.println(sb);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. SWEA 보급로 문제의 열화판 (링크)

1. BFS를 이용해 1,1부터 N,M까지 탐색

* 1,1 노드부터 N,M노드까지 최소 거리를 구하는 다익스트라로 풀이 가능

  - 노드의 값 = 노드까지의 cost

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int[] dx = {1,0,-1,0};
	static int[] dy = {0,1,0,-1};
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int M = pint(st.nextToken());
		int N = pint(st.nextToken());
		int[][] map = new int[N+2][M+2];
		int[][] cost = new int[N+2][M+2];
		
		//외곽설정, cost초기화
		for (int i = 0; i < N+2; i++) {
			map[i][0]=-1;map[i][M+1]=-1;
			Arrays.fill(cost[i], Integer.MAX_VALUE);
		}
		for (int i = 0; i < M+2; i++) {
			map[0][i]=-1;map[N+1][i]=-1;
		}
		
		//입력받기
		for (int i = 0; i < N; i++) {
			String s = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i+1][j+1]=s.charAt(j)-'0';
			}
		}
		
		Queue<int[]> qu = new LinkedList<>();
		qu.offer(new int[] {1,1});
		cost[1][1]=0;
		
		while(!qu.isEmpty()) {
			int[]cur = qu.poll();
			int curCost = cost[cur[0]][cur[1]];
			//더 작은 코스트로 진행할 수 있다면
			for (int i = 0; i < 4; i++) {
				int tx=cur[0]+dx[i], ty=cur[1]+dy[i];
				
				if(map[ tx ][ ty ]!=-1 && curCost + map[ tx ][ ty ] < cost[ tx ][ ty ]) {
					qu.offer(new int[] {tx, ty});
					cost[ tx ][ ty ]=curCost+map[ tx ][ ty ];
				}
			}
		}
		System.out.println(cost[N][M]);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 작은사람 -> 큰 사람 정보를 단방향 그래프로 표현

1. 플로이드 와샬 실행, 모든 노드에 대해 최솟값을 구한다

2. n번째 학생의 키 순서를 알기 위해선, 다른 모든 학생 k에 대해

  - k가 n보다 크거나 : n->k로 가는 길이 존재

  - n이 k보다 크거나 : k->n으로 가는 길이 존재

  - 둘 중 하나를 만족해야한다

3. 인접행렬의 adj[k][n] 혹은 adj[n][k] 둘 중 하나의 길이 존재해야한다

  - 두 값이 다 초깃값을 유지하고있다면 알 수 없음, 세지 않는다

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

public class Main{
	final static int maxV = 100000;

	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int[][]adj = new int[n][n];
		for (int i = 0; i < n; i++) {
			Arrays.fill(adj[i], maxV);
		}
		//방향 그래프
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int s = pint(st.nextToken())-1;
			int b = pint(st.nextToken())-1;
			adj[s][b]=1;
		}
		//플로이드
		for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					adj[i][j]=Math.min(adj[i][j], adj[i][k]+adj[k][j]);
				}
			}
		}
		//조건을 만족하는 학생 카운트
		int cnt=0;

		for (int i = 0; i < n; i++) {
			adj[i][i]=0;
			boolean chk=true;
			for (int j = 0; j < n; j++) {
				if(Math.min(adj[i][j],adj[j][i])==maxV) {
					chk=false;
					break;
				}
			}
			if(chk)cnt++;
		}
		
		System.out.println(cnt);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. CCTV의 종류에 따라 가능한 모든 경우의 수를 해보는 브루트-포스 문제

  - 종류별로 가능한 탐색 방향을 미리 저장

1. 2/5번 CCTV는 회전 중 동일한 입력이 있으므로 제거해준다

  - 하지 않아도 통과하는데는 문제 없음

2. 매 CCTV마다, 가능한 모든 방향으로 감시해보며 다음으로 진행

  - 빈 공간(사각지대)의 개수를 유지, 최솟값 저장

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

public class Main{
	static int eArea, min=Integer.MAX_VALUE;
	static int[][] map;
	static ArrayList<int[]>cctv;
	static ArrayList<ArrayList<int[][]>>move;
	static void init() {
		move= new ArrayList<>();
		for (int i = 0; i <= 5; i++) {
			move.add(new ArrayList<>());
		}
		move.get(1).add(new int[][] {{1,0}});
		move.get(1).add(new int[][] {{0,1}});
		move.get(1).add(new int[][] {{-1,0}});
		move.get(1).add(new int[][] {{0,-1}});
		
		move.get(2).add(new int[][] {{0,-1},{0,1}});
		move.get(2).add(new int[][] {{1,0},{-1,0}});
		
		move.get(3).add(new int[][] {{1,0},{0,1}});
		move.get(3).add(new int[][] {{-1,0},{0,1}});
		move.get(3).add(new int[][] {{-1,0},{0,-1}});
		move.get(3).add(new int[][] {{1,0},{0,-1}});
		
		move.get(4).add(new int[][] {{1,0},{0,1},{-1,0}});
		move.get(4).add(new int[][] {{0,-1},{0,1},{-1,0}});
		move.get(4).add(new int[][] {{0,-1},{1,0},{-1,0}});
		move.get(4).add(new int[][] {{0,-1},{1,0},{0,1}});
		
		move.get(5).add(new int[][] {{-1,0},{0,-1},{1,0},{0,1}});
	}
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		init();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		
		map = new int[n+2][m+2];
		cctv=new ArrayList<>(); 
		for (int i = 0; i < n+2; i++) {
			map[i][0]=6; map[i][m+1]=6;
		}for (int i = 0; i < m+2; i++) {
			map[0][i]=6; map[n+1][i]=6;
		}
		for (int i = 1; i <= n; i++) {
			st=new StringTokenizer(br.readLine()," ");
			for (int j = 1; j <= m; j++) {
				map[i][j]=pint(st.nextToken());
				
				if(map[i][j]==0)eArea++;
				else if(map[i][j]!=6)cctv.add(new int[] {i,j});
			}
		}
		rec(0);
		System.out.println(min);
	}
	static void rec(int cnt) {
		if(cnt==cctv.size()) {
			min=Math.min(min, eArea);
			return;
		}
		
		int[][]mapBU=new int[map.length][map[0].length];
		for (int x = 0; x < map.length; x++)
			for (int y = 0; y < map[0].length; y++)
				mapBU[x][y]=map[x][y];
		int eAreaBU=eArea;
		
		int[] cur=cctv.get(cnt);
		int curV = map[cur[0]][cur[1]];
		
		for (int i = 0; i < move.get(curV).size(); i++) {
			for (int x = 0; x < map.length; x++)
				for (int y = 0; y < map[0].length; y++)
					map[x][y]=mapBU[x][y];
			eArea=eAreaBU;
			
			for (int j = 0; j < move.get(curV).get(i).length; j++) {
				int[]dir = move.get(curV).get(i)[j];
				int tx = cctv.get(cnt)[0]+dir[0], ty=cctv.get(cnt)[1]+dir[1];
				while(map[tx][ty]!=6) {
					if(map[tx][ty]==0) {
						map[tx][ty]=7;
						eArea--;
					}
					tx+=dir[0];
					ty+=dir[1];
				}
			}
			rec(cnt+1);
		}
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 1019번, 책 페이지의 코드 재사용 (링크)

1. 두 페이지까지의 숫자를 구해 합을 구하고, 그 차이를 구한다

  - L페이지는 포함되야 하므로, 따로 합해준다

* SWEA 5604번 구간합 문제와 거의 동일하다 (링크)

  - 출력 양식 수정 후 반복문만 돌리면 통과

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

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		String n = st.nextToken();
		String m = st.nextToken();
		long temp = page(m)-page(n);
		for (int i = 0; i < n.length(); i++)temp+=n.charAt(i)-'0';
		System.out.println(temp);
	}
	
	static long page(String N) {
		long returnVal=0;
		long[]page = new long[10];
		long[]prev = new long[10];
		long[]ans = new long[10];

		int len = N.length();
		
		ArrayList<long[]>index=new ArrayList<>();
		index.add(page.clone());
		long cnt=1;
		//전처리
		for (int i = 0; i <= len; i++) {
			for (int j = 0; j <= 9; j++) {
				page[j]*=10;
				page[j]+=cnt;
			}
			index.add(page.clone());
			cnt*=10;
		}
		
		//0번 자리부터
		for (int i = 0; i < N.length(); i++, len--) {
			int cur = N.charAt(i)-'0';

			long[] curIdx = index.get(len-1);
			long repeat = (long)Math.pow(10, len-1);
			for (int j = 0; j <= 9; j++) {
				ans[j]+=curIdx[j]*cur;
				ans[j]+=prev[j]*repeat*cur;//prev처리
			}
			
			//가장 앞자리 처리
			for (int j = 0; j < cur; j++) {
				ans[j]+=repeat;
			}
			
			prev[cur]++;
		}
		for (int j = 0; j <= 9; j++) ans[j]+=prev[j];
		for (int i = 0; i < N.length(); i++) ans[0]-=Math.pow(10, i);
		for (int i = 0; i <= 9; i++) {
			returnVal+=i*ans[i];
		}
		return returnVal;
	}
	
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. state 클래스로 정보를 관리 (x좌표, y좌표, 이전이동, 이동횟수)

1. bfs처럼 진행하되, 항상 목표지점으로 다가가는 이동이 최적의 이동이다

  - 현재 좌표와 목표좌표를 비교, 나아가야 할 방향을 결정한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution{
	
	static class state {
		public int x,y,prev,cost;
		public state(int x, int y, int prev, int cost) {
			super();
			this.x = x;
			this.y = y;
			this.prev = prev;
			this.cost = cost;
		}
	}
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int sx = pint(st.nextToken());
			int sy = pint(st.nextToken());
			int dx = pint(st.nextToken());
			int dy = pint(st.nextToken());
			
			Queue<state>qu=new LinkedList<>();
			
			if(sx==dx && sy==dy) {
				sb.append("#").append(testcase).append(" ").append(0).append("\n");
				continue;
			}
			
			if(sx<dx)qu.offer(new state(sx+1,sy,1,1));
			else qu.offer(new state(sx-1,sy,1,1));
			if(sy<dy)qu.offer(new state(sx,sy+1,2,1));
			else qu.offer(new state(sx,sy-1,2,1));
			
			while(true) {
				state cur = qu.poll();
				System.out.println(cur.x+" "+cur.y);
				if(cur.x==dx && cur.y==dy) {
					sb.append("#").append(testcase).append(" ").append(cur.cost).append("\n");
					break;
				}
				
				if(cur.prev==2) {
					if(cur.x<dx)qu.offer(new state(cur.x+1, cur.y, 1, cur.cost+1));
					else qu.offer(new state(cur.x-1, cur.y, 1, cur.cost+1));
				}
				else {
					if(cur.y<dy)qu.offer(new state(cur.x, cur.y+1, 2, cur.cost+1));
					else qu.offer(new state(cur.x, cur.y-1, 2, cur.cost+1));
				}
				
			}
		}System.out.println(sb);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}