[백준] 욕심쟁이 판다 (java) Dynamic_programming

2020-04-03

욕심쟁이 판다 (백준> Dynamic_programming)

문제 링크

문제설명

n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-)

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 살 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n*n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 오래 살려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력

첫째 줄에 대나무 숲의 크기 n(1 ≤ n ≤ 500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에는 판다가 최대한 살 수 있는 일수(K)를 출력한다.

예제 입력 1 복사

4
14 9 12 10
1 11 5 4
7 15 2 13
6 3 16 8

예제 출력 1 복사

4


풀이

package Dynamic_programming;

import java.util.Scanner;

public class beak_욕심쟁이판다 {
	static int arr[][];
	static int dp[][];
	static int n;
	
	public static int move(int x, int y) {
        //한군데라도 다녀왔다면 끝까지 가서 답을 가지고 있기 때문에 memoization
		if(dp[x][y] !=0)
			return dp[x][y];
		

		//기저조건에 안걸려서 for문에 들어가겠다는 뜻은 첫날이라는 뜻이다
		int dx[] = {0,0,1,-1};
		int dy[] = {1,-1,0,0};
		
        //일단 1을 넣어주고 시작하겠다
		dp[x][y] = 1;
		
		for(int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx>=0 && nx<n && ny>=0 && ny<n) {
				if(arr[nx][ny] > arr[x][y]) {
                    //돌아오면서 +1 해주고, 맨끝에 도달한 곳의 값은 1이다.
                    //또한, 여러 갈래에서 온 값 중 큰 값을 가져야하기때문에 Math.max()로 비교
				  dp[x][y] = Math.max(dp[x][y], move(nx,ny)+1);
				}
			}
		}
		
		return dp[x][y];
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		
		arr = new int[n][n];
		
		sc.nextLine();
		
		for(int i=0;i<n; i++) {
			String s = sc.nextLine();
			String ss[] = s.split(" ");
			for(int j=0;j<n; j++)
				arr[i][j] = Integer.parseInt(ss[j]);
		}


		int answer = 0;
		dp = new int[n][n];
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++)
				answer = Math.max(answer, move(i,j)); // 전부 다 돈다
		}
		

		
		System.out.println(answer);
		
	}
}

후기 (1h)

전부 다 돌아야 한다고 dfs로 풀기에는 힘들었고…

DP로 푸는 방법을 찾다가,

  1. 갈 수 있는 곳은 계속 끝까지 가면서 1로 만들고
  2. 돌아오는 길에 +1해주면서 그 값과 원래 값의 MAX를 DP값에 넣어주고
  3. Memoization을 통해, 값이 저장돼있으면 끝까지 돌지 않고, 바로 return
Read More

[백준] 신입사원 (java) Greedy

2020-04-03

신입사원 (백준> Greedy)

문제 링크

문제설명

언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.

그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.

출력

각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

2
5
3 2
1 4
4 1
2 3
5 5
7
3 6
7 3
4 2
1 4
5 7
2 5
6 1

예제 출력 1 복사

4
3


풀이

package Greedy;

import java.util.*;

public class beak_신입사원 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		for(int i=0; i<n;i++) {
			int m = sc.nextInt();
			
			int arr[][] = new int[m][2];
			
			for(int j=0; j<m; j++) {
				arr[j][0] = sc.nextInt();
				arr[j][1] = sc.nextInt();
			}
			
			Arrays.sort(arr, new Comparator<int[]>() {
				@Override
				public int compare(int a[], int b[]) {
					return a[0] - b[0]; // 0번쨰 행으로 오룸차순
				}
			}); // 오름차순 정렬

			int answer = 0;
			int min = Integer.MAX_VALUE;
			
			for(int j=0; j<arr.length; j++) {
				if(min>arr[j][1]) {
					min = arr[j][1];
					answer++;
				}
			}
			
			
			System.out.println(answer);
		}
	}
}

후기 (1h)

완탐으로 풀어서 당연히 시간초과…!ㅎㅎ

  1. 서류성적으로 오름차순 정렬을 한 후,
  2. 면접성적은 내려갈수록 현재 min보다 작아야하고 그 때 answer++ 해준다

첨 풀었을땐 아래처럼 풀었다

package Greedy;

import java.util.*;

public class beak_신입사원 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		for(int i=0; i<n;i++) {
			int m = sc.nextInt();
			
			int arr[][] = new int[m][2];
			
			for(int j=0; j<m; j++) {
				arr[j][0] = sc.nextInt();
				arr[j][1] = sc.nextInt();
			}
			
			Arrays.sort(arr, new Comparator<int[]>() {
				@Override
				public int compare(int a[], int b[]) {
					return a[0] - b[0];
				}
			}); // 오름차순 정렬

			int answer = 0;
			
			for(int j =arr.length-1; j>=0; j--) {
				int now = arr[j][1];
				boolean ck = false;
				
				for(int k = j-1; k>=0; k--) {
					if(now > arr[k][1]) {//나보다 작은게 하나라도 있으면
						ck =true;
						break;
					}
				}
				
				if(ck == false)
					answer++;
			}
			
			System.out.println(answer);
		}
	}
}
Read More

[백준] 회의실 배정 (java) Sort

2020-04-02

회의실 배정 (백준> Sort)

문제 링크

문제설명

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력 1 복사

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력 1 복사

4


풀이

package Sort;

import java.util.*;

public class beak_회의실배정 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int arr[][] = new int[n][2];
		
		for(int i=0;i<n; i++) {
			arr[i][0] = sc.nextInt();
			arr[i][1] = sc.nextInt();
		}
		
		Arrays.sort(arr, new Comparator<int[]>() {
			@Override
			public int compare(int a[], int b[]) {
				if(a[1] == b[1])
					return a[0] - b[0]; // 오름차순
				else
					return a[1] - b[1]; // 오름차순
			}
		});
		
		
		int answer = 1;
		int now = arr[0][1];
		
		for(int i=1; i<n; i++) {
			if(arr[i][0] >= now){
				answer++;
				now = arr[i][1];
			}
		}//for
		
		System.out.println(answer);
	}
}

후기 (20min)

다시 풀면서도 까먹음… 앞으로 정렬할지, 뒤로 정렬 할지 잘 생각하고 문제풀기

Read More

[백준] 좌표 정렬하기 (java) Sort

2020-04-02

좌표 정렬하기 (백준> Sort)

문제 링크

문제설명

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

예제 입력 1 복사

5
3 4
1 1
1 -1
2 2
3 3

예제 출력 1 복사

1 -1
1 1
2 2
3 3
3 4


풀이

package Sort;

import java.util.*;

public class beak_좌표정렬하기 {
	
	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int arr[][] = new int[n][2];
		
		for(int i=0;i<arr.length; i++) {
			arr[i][0] = sc.nextInt();
			arr[i][1] = sc.nextInt();
		}
		
		Arrays.sort(arr, new Comparator<int[]>() {
			@Override
			public int compare(int a[], int b[]){
				if(a[0] == b[0]) //0번째 행렬이 같을 때는
					return a[1]- b[1]; // 뒤에거로 오름차순
				else
					return a[0] - b[0]; //0번째행렬로 오름차순
			}
		});
		
//		Arrays.sort(arr, new Comparator<int[]>() {
//			@Override
//			public int compare(int a[], int b[]){
//				if(a[0] == b[0]) //0번째 행렬이 같을 때는
//					return b[1]- a[1]; // 뒤에거로 내림차순
//				else
//					return b[0] - a[0]; //0번째행렬로 내림차순
//			}
//		});
//		
//		Arrays.sort(arr, new Comparator<int[]>() {
//			@Override
//			public int compare(int a[], int b[]){
//				if(a[0] == b[0]) //0번째 행렬이 같을 때는
//					return a[1]-b[1]; // 뒤에거로 오림차순
//				else
//					return b[0] - a[0]; //0번째행렬로 내림차순
//			}
//		});
		
		
		for(int i=0; i<n; i++) {
			System.out.println(arr[i][0] + " " + arr[i][1]);
		}
	}
}

후기 (20min)

Comparator 쓰는 법 제대로 익힘!!

Read More

[백준] 이동하기 (java) Dynamic_programming

2020-03-31

이동하기 (백준> Dynamic_programming)

문제 링크

문제설명

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

예제 입력 1 복사

3 4
1 2 3 4
0 0 0 5
9 8 7 6

예제 출력 1 복사

31

예제 입력 2 복사

3 3
1 0 0
0 1 0
0 0 1

예제 출력 2 복사

3

예제 입력 3 복사

4 3
1 2 3
6 5 4
7 8 9
12 11 10

예제 출력 3 복사

47

풀이

package Dynamic_programming;

import java.util.*;

public class beak_이동하기 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		int arr[][] = new int[n][m];
		
		sc.nextLine();
		
		for(int i=0;i<n; i++) {
			String s = sc.nextLine();
			String ss[] = s.split(" ");
			
			for(int j=0; j<ss.length; j++)
				arr[i][j] = Integer.parseInt(ss[j]);
		}
		
		for(int i=1; i<m; i++) //0행 계산
			arr[0][i] = arr[0][i] + arr[0][i-1];
		
		for(int i=1; i<n; i++) //0열 계산
			arr[i][0] = arr[i][0] + arr[i-1][0];
		
		for(int i=1; i<n; i++) {
			for(int j=1; j<m; j++) {
				arr[i][j] = arr[i][j] + Math.max(arr[i][j-1], Math.max(arr[i-1][j], arr[i-1][j-1]));
			}
		}
		
		System.out.println(arr[n-1][m-1]);
		
	}
}

후기 (10min)

오랜만의 쉬운 dp 문제! 벽에 붙은 0행과 0열은 전의 값만 가질 수 있으니 더해주고,

나머지는 내 앞, 내 밑, 내 위의 대각선 중 max 값 선택해서 더해준다

Read More