'분류 전체보기' 카테고리의 글 목록 (49 Page)

코드

실패 코드 : DP 분류에 있는 문제를 눌렀는데 bfs로 풀 수 있는 문제 같아서 bfs로 구현해 보았다. 결과는 시간초과..

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

public class Main {
	static int[] x = { 1, 0, 1 };
	static int[] y = { 0, 1, 1 };
	static int N, M, max = 0;
	static int[][] array;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		array = new int[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++)
				array[i][j] = Integer.parseInt(st.nextToken());
		}
		bfs(0, 0, 0);

		System.out.println(max);
	}

	static void bfs(int a, int b, int count) {
		count += array[a][b];

		if (a == N - 1 && b == M - 1) {
			if (count > max)
				max = count;
			return;
		}

		for (int direction = 0; direction < 3; direction++) {
			int r = a + x[direction];
			int c = b + y[direction];

			if (r >= 0 && c >= 0 && r < N && c < M)
				bfs(r,c,count);
		}
	}

}

설명 : dp문제 답게 dp로 풀었다. 사진에서 보듯이 현재 위치에서 (-1,-1), (-1,0), (0,-1) 한 위치의 값들 중 가장 큰값을 현재 위치의 값과 더 해준다. 이렇게 (N, M)까지 반복문을 돌리면 N, M 위치엔 (0, 0)위치에서 (+1,0), (0,+1), (+1, +1)하면서 더해준 값 중 가장 큰 값이 저장되어 있는다.

정답 코드 : 위에서 쓴 식으로 풀어낸 코드이다.

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[][] array = new int[N+1][M+1];

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= M; j++)
				array[i][j] = Integer.parseInt(st.nextToken());
		}
		
		
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) 
				array[i][j] += Math.max(array[i-1][j-1], Math.max(array[i-1][j], array[i][j-1]));
		}
		
		System.out.println(array[N][M]);
	}

}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 11054번 : 가장 긴 바이토닉 부분 수열 (0)	2020.10.11
[JAVA] 백준 1013번 : Contact (0)	2020.10.09
[JAVA] 백준 17070번 : 파이프 옮기기 1 (0)	2020.10.07
[JAVA] 백준 11051번 : 이항 계수 2 (0)	2020.10.06
[JAVA] 백준 1991번 : 트리 순회 (0)	2020.10.05

코드

정답 코드 : (0,1) 가로 일 때부터 시작해서 45도로만 움직일 수 있게 재귀문으로 반복해주면서 (N,N)까지 도달했을 때만 count++ 해줌.

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

public class Main {	
	static int[][] array;
	static int N;
	static int count;
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		N = Integer.parseInt(br.readLine());
		array = new int[N+1][N+1];
		count = 0;
		
		for(int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 1; j <= N; j++) {
				 array[i][j] = Integer.parseInt(st.nextToken());
			}
		}		
		
		RecurPipe(1, 2, 0);

		System.out.println(count);
    }
	
	private static void RecurPipe(int x, int y, int type) {
		if(x == N && y == N && array[x][y] != 1) {
			count++;
			return;
		}
		
		// 가로
		if(type == 0) {
			// 오른쪽
			if(check(x, y+1) && array[x][y+1] == 0) 
				RecurPipe(x, y+1, 0);			
			// 오른쪽 아래 대각선
			if(check(x+1, y+1) && array[x+1][y+1] == 0 && array[x+1][y] == 0 && array[x][y+1] == 0) 
				RecurPipe(x+1, y+1, 2); 
			
		} else if(type == 1) { // 세로
			// 밑
			if(check(x+1, y) && array[x+1][y] == 0) 
				RecurPipe(x+1, y, 1);			
			// 오른쪽 아래 대각선
			if(check(x+1, y+1) && array[x+1][y+1] == 0 && array[x+1][y] == 0 && array[x][y+1] == 0) 
				RecurPipe(x+1, y+1, 2);
			
		} else if(type == 2) {	// 대각
			// 가로
			if(check(x, y+1) && array[x][y+1] == 0) 
				RecurPipe(x, y+1, 0);			
			// 세로
			if(check(x+1, y) && array[x+1][y] == 0) 
				RecurPipe(x+1,y, 1);			
			// 그대로 대각선
			if(check(x+1, y+1) && array[x+1][y+1] == 0 && array[x+1][y] == 0 && array[x][y+1] == 0) 
				RecurPipe(x+1,y+1,2);
		}
	}
	
	private static boolean check(int x, int y) {
		return x>=1 && x<=N && y>=1 && y<=N;
	}
}

다른 사람 코드 : 점화식을 이용해서도 풀 수 있다는 것을 보여준다.

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

class Main
{
	
	public static void main(String args[]) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		int[][] map = new int[n][n];
		long[][][] dp = new long[n][n][3];
		
		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());
			}
		}
		dp[0][1][0] = 1;
		for(int i=0;i<n;++i) {
			for(int j=0;j<n;++j) {
				//가로 => 대각선 + 가로
				if(j+1 < n && map[i][j+1] == 0) 
					dp[i][j+1][0] += dp[i][j][1] + dp[i][j][0];
				
				//대각선 => 대각선 + 가로 + 세로
				if(j+1<n && i+1 < n && map[i+1][j] == 0 && map[i+1][j+1] == 0 && map[i][j+1] == 0)  
					dp[i+1][j+1][1] += dp[i][j][0] + dp[i][j][1] + dp[i][j][2];
				
				//세로 => 대각선 + 세로
				if(i+1<n && map[i+1][j] == 0) 
					dp[i+1][j][2] += dp[i][j][1] + dp[i][j][2];
			}
		}
		
		System.out.println(dp[n-1][n-1][0] + dp[n-1][n-1][1] + dp[n-1][n-1][2]);
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 1013번 : Contact (0)	2020.10.09
[JAVA] 백준 11048번 : 이동하기 (0)	2020.10.09
[JAVA] 백준 11051번 : 이항 계수 2 (0)	2020.10.06
[JAVA] 백준 1991번 : 트리 순회 (0)	2020.10.05
[JAVA] 백준 12865번 : 평범한 배낭 (0)	2020.10.05

코드

정답 코드 : qazyj.tistory.com/95를 참고해서 다시 한번 비슷한 문제를 되새김하는 느낌으로 풀어봄.

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

public class Main {
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        long[] factorial = new long[N+1];
        factorial[0] = 1;
        factorial[1] = 1;
       
        for(int i=2; i<=N; i++) factorial[i] = (factorial[i-1]*i)%10007;
        long denominator = (factorial[K]*factorial[N-K])%10007;

        long index = 10007-2;
        long fermatNum = 1;
        while(index > 0){
            if(index%2==1){
                fermatNum *= denominator;
                fermatNum %= 10007;
            }
            denominator = (denominator*denominator)%10007;
            index /= 2;
        }
        long result = ((factorial[N]%10007)*(fermatNum%10007))%10007;
        System.out.print(result);

    }
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 11048번 : 이동하기 (0)	2020.10.09
[JAVA] 백준 17070번 : 파이프 옮기기 1 (0)	2020.10.07
[JAVA] 백준 1991번 : 트리 순회 (0)	2020.10.05
[JAVA] 백준 12865번 : 평범한 배낭 (0)	2020.10.05
[JAVA] 백준 11401번 : 이항 계수 3 (0)	2020.10.04

코드

정답 코드 : 처음 풀어 본 트리 문제이다. 노드 클래스를 생성하여서 클래스 배열로 접근하였다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static class NODE {
		String val;
		int parent, right, left;

		public NODE(String val) {
			this.val = val;
			this.parent = this.right = this.left = -1;
		}
	};

	static int N;
	static NODE array[];
	static String s;

	static void preOrder(int node) {
		System.out.print(array[node].val);
		if (array[node].left > -1)
			preOrder(array[node].left);
		if (array[node].right > -1)
			preOrder(array[node].right);
	}

	static void inOrder(int node) {
		if (array[node].left > -1)
			inOrder(array[node].left);
		System.out.print(array[node].val);
		if (array[node].right > -1)
			inOrder(array[node].right);
	}

	static void postOrder(int node) {
		if (array[node].left > -1)
			postOrder(array[node].left);
		if (array[node].right > -1)
			postOrder(array[node].right);
		System.out.print(array[node].val);
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		array = new NODE[26];
		N = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < 26; i++) {
			array[i] = new NODE(Character.toString((char) (i + 'A')));
		}
		
		for (int i = 0; i < N; i++) {
			char a, b, c;
			s = br.readLine();
			a = s.charAt(0);
			b = s.charAt(2);
			c = s.charAt(4);
			if (b != '.') {
				array[a - 'A'].left = b - 'A';
				array[b - 'A'].parent = a - 'A';
			}
			if (c != '.') {
				array[a - 'A'].right = c - 'A';
				array[c - 'A'].parent = a - 'A';
			}
		}
		preOrder(0);
		System.out.println();
		inOrder(0);
		System.out.println();
		postOrder(0);
		System.out.println();
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 17070번 : 파이프 옮기기 1 (0)	2020.10.07
[JAVA] 백준 11051번 : 이항 계수 2 (0)	2020.10.06
[JAVA] 백준 12865번 : 평범한 배낭 (0)	2020.10.05
[JAVA] 백준 11401번 : 이항 계수 3 (0)	2020.10.04
[JAVA] 백준 10989번 : 수 정렬하기 3 (0)	2020.10.04

코드

정답 코드 : st-lab.tistory.com/141를 통해 이해한 바로 작성하였다.

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
 
		int[] weight = new int[N + 1];
		int[] value = new int[N + 1]; 
		int[] dp = new int[K + 1];
 
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			weight[i] = Integer.parseInt(st.nextToken());
			value[i] = Integer.parseInt(st.nextToken());
		}
 
		for (int i = 1; i <= N; i++) {
			for (int j = K; j - weight[i] >= 0; j--) {
				dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
			}
		}
		System.out.println(dp[K]);
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 11051번 : 이항 계수 2 (0)	2020.10.06
[JAVA] 백준 1991번 : 트리 순회 (0)	2020.10.05
[JAVA] 백준 11401번 : 이항 계수 3 (0)	2020.10.04
[JAVA] 백준 10989번 : 수 정렬하기 3 (0)	2020.10.04
[JAVA] 백준 11052번 : 카드 구매하기 (0)	2020.09.30

코드

정답 코드 : onsil-thegreenhouse.github.io/programming/problem/2018/04/02/problem_combination/를 참고해서 이해하였다.

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

public class Main {
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        long[] factorial = new long[N+1];
        factorial[0] = 1;
        factorial[1] = 1;
       
        for(int i=2; i<=N; i++) factorial[i] = (factorial[i-1]*i)%1000000007;
        long denominator = (factorial[K]*factorial[N-K])%1000000007;

        long index = 1000000007-2;
        long fermatNum = 1;
        while(index > 0){
            if(index%2==1){
                fermatNum *= denominator;
                fermatNum %= 1000000007;
            }
            denominator = (denominator*denominator)%1000000007;
            index /= 2;
        }
        long result = ((factorial[N]%1000000007)*(fermatNum%1000000007))%1000000007;
        System.out.print(result);

    }
}

정답 코드 : 위의 코드보다 메모리도 1/4정도 잡아먹고, 속도도 위의 코드보다 좀 더 빠르다. 페르마의 소정리를 이용ㅇ해서 푼 코드이다.

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

/* [페르마의 소정리] _ 혜민 코드 참고
a^(p-1) % p = 1
(a/b) % M = ((a % M) * (b^-1 % M)) = ((a % M) * (b^(M-2) % M))
*/

public class Main {
    static final int MOD = 1000000007;
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        long a = fac(N);
        long b = fac(N - K) * fac(K) % MOD;
        long result = a * pow(b, MOD - 2) % MOD;
        System.out.print(String.valueOf(result));
        
    }

    public static long fac(long n) {
        long result = 1;
        while (n > 1) {
            result = (result * n) % MOD;
            n--;
        }
        return result;
    }

    public static long pow(long a, int b) {
        long result = 1;
        long temp = a;

        while (b > 0) {
            if (b % 2 == 1) result = result * temp % MOD;
            b = b / 2;
            temp = (temp * temp) % MOD;
        }

        return result;
    }
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 1991번 : 트리 순회 (0)	2020.10.05
[JAVA] 백준 12865번 : 평범한 배낭 (0)	2020.10.05
[JAVA] 백준 10989번 : 수 정렬하기 3 (0)	2020.10.04
[JAVA] 백준 11052번 : 카드 구매하기 (0)	2020.09.30
[JAVA] 백준 1932번 : 정수 삼각형 (0)	2020.09.29

코드

실패 코드 : 시간 초과

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

public class Main {
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] array = new int[N];
		
		for(int i = 0; i < N; i++) {
			array[i] = Integer.parseInt(br.readLine());
			
			for(int j = i - 1; j >= 0; j--) {
				if(array[j] > array[j+1]) {
					int temp = array[j];
					array[j] = array[j+1];
					array[j+1] = temp;
				} else break;
			}
		}
		
		for(int i = 0; i < N; i++)
			System.out.println(array[i]);
	}
}

실패 코드 : 메모리 초과 append(array[i] + "\n")를 append(array[i]).append("\n")로 바꾸니까 메모리 초과가 안뜨긴 함.

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

public class Main {
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		int[] array = new int[N];
		
		for(int i = 0; i < N; i++) 
			array[i] = Integer.parseInt(br.readLine());
			
		Arrays.sort(array);
		
		for(int i = 0; i < N; i++)
			sb.append(array[i] + "\n");
		System.out.print(sb);
	}
}

성공 코드 : Arrays.sort를 써서 그런지 생각보다 속도가 느리다.

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

public class Main {
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		int[] array = new int[N];
		
		for(int i = 0; i < N; i++) 
			array[i] = Integer.parseInt(br.readLine());
			
		Arrays.sort(array);
		
		for(int i = 0; i < N; i++)
			sb.append(array[i]).append("\n");
		System.out.println(sb);
	}
}

성공 코드 : 위의 것에서 array.sort를 쓰지 않고 인덱스에 해당 숫자를 ++해주면서 출력 해주는 코드이다. 위의 코드보다 1/3 정도 더 빠르게 나온다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Algorithm {
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
        int[] array = new int[10001];
        
        for (int i = 0; i < N; i++) 
            array[Integer.parseInt(br.readLine())] ++;
         
        for (int i = 1; i <= 10000; i++) {
            if (array[i] > 0) { 
                for (int j = 0; j < array[i]; j++) 
                    sb.append(i).append("\n");                
            }
        }
        System.out.print(sb);
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 12865번 : 평범한 배낭 (0)	2020.10.05
[JAVA] 백준 11401번 : 이항 계수 3 (0)	2020.10.04
[JAVA] 백준 11052번 : 카드 구매하기 (0)	2020.09.30
[JAVA] 백준 1932번 : 정수 삼각형 (0)	2020.09.29
[JAVA] 백준 2225번 : 합분해 (0)	2020.09.23

코드

정답 코드 :

민규가 구매하려고 하는 카드의 개수 N = 4, P1 = 1, P2 = 5, P3 = 6, P4 = 7

n개의 카드를 갖기 위해 지불하는 금액의 최댓값을 dp[n]이라고 할 때, 민규가 카드 1개를 갖는다고 한다면 dp[1] = p1이다.

민규가 카드 2개를 갖는다고 한다면 2개가 들어있는 카드팩 1개를 사던가, 1개짜리 카드팩 2개를 사는 경우이다.

dp[2] = MAX(P[2], dp[1] + dp[1])

만약 민규가 카드 3개를 갖는다고 한다면 3개가 들어있는 카드팩을 1개 사던가, 2개짜리 카드팩과 1개짜리 카드팩을 각각 하나씩 사던가, 아니면 1개짜리 카드팩 3개를 사는 경우로 dp[3] = MAX(P[3], dp[2] + dp[1], dp[1] *3)

dp[1] * 3 은 dp[1] * 2 + dp[1]과 같다. dp[2] + dp[1] 과 dp[1] * 2 + dp[1]을 비교할 때, dp[2]와 dp[1] * 2의 비교가 된다.

앞서 dp[2]의 값을 넣을 때 P[2]와 dp[1] * 2 중 큰 값을 dp[2]에 넣었을 때, dp[3] = MAX(P[3], dp[2] + dp[1]) 이다.

마지막으로 민규가 카드 4개를 갖는다고 할 때, dp[4] = MAX(P[4], dp[3] + dp[1], dp[2] + dp[2]) 이다.

따라서, 점화식은 dp[n] = MAX(P[n], dp[n - 1] + dp[1], dp[n - 2] + dp[2] ..., dp[n - n/2] + dp[n/2])

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] array = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            array[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[N + 1];

        dp[1] = array[1];

        for(int i = 2; i <= N; i++) {
            dp[i] = array[i];
            for(int j = 0; j <= i / 2; j++)
                dp[i] = Math.max(dp[i], dp[i - j] + dp[j]);
        }

        System.out.println(dp[N]);
    }
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 11401번 : 이항 계수 3 (0)	2020.10.04
[JAVA] 백준 10989번 : 수 정렬하기 3 (0)	2020.10.04
[JAVA] 백준 1932번 : 정수 삼각형 (0)	2020.09.29
[JAVA] 백준 2225번 : 합분해 (0)	2020.09.23
[JAVA] 백준 9252번 : LCS 2 (0)	2020.09.22

선장 일지