연습문제 (66) 썸네일형 리스트형 [백준] 4179 - 불! (java) 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 풀이 방법 (BFS) 다음과 같은 순서로 문제를 풀었다 1. J가 동서남북으로 이동할 수 있는 경로를 찾아 이동 위치를 찾고 큐에 넣는다 2. J가 전부 한번 이동 후 불이 번진다. (for문으로 이전에 넣은 불만 번지게 하도록 한다) 3. 1에서 넣은 위치가 불이 번진 위치라면 건너뛴다 J가 불을 피해서 미로의 끝에 도달하면 성공으로 처리하여 구현하였다. 문제를 풀면서 주의할 점은 1. J가 먼저 이동하고 그다음 불이 번진다. 2. J가 이동하고.. [백준] 2225 - 합분해 (java) 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 두 정수 n과 k를 입력받는다 여기서 n은 만드려고 하는 수, k는 n을 만들기 위해 사용하는 수의 갯수이다. 0부터 n까지 정수 k개를 더해서 합이 n이 되는 경우의 수를 구한다. 만약 입력값이 4 2 라면 1 3 3 1 4 0 0 4 2 2 이렇게 5가지가 된다 문제 풀이 우리가 구하는 경우의 수를 k와 n에 따라 dp에 저장하기 위해 dp[k+1][n+1] 배열을 만들었다. 1. n = 0일때 (만드려는 수가 0) 만드려는 수(n)가 0이면 자릿수(k)가 어떻게 되던지 1가지 방법이 나온다. (n = 0 , k = 3 이면 0 0 0으로 한가지 n = 0, k = 4면 0 0 .. [백준] 9095 - 1,2,3더하기 (java) 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제내용 첫번째 줄은 테스트 케이스 수이고 두번째 줄부터 각 테스트 정수 n이 주어진다. 1,2,3의 합으로 정수 n을 구하는 수를 출력하자. (한개 이상 수를 사용해야한다) 문제풀이 아래는 1부터 4까지 가지는 조합의 수이다. n=1 : 1 n=2 : 1+1 2 n=3 : 1+1+1 2+1 1+2 3 n=4 : 1+1+1+1 // (n-1)+1 1+2+1 2+1+1 3+1 1+1+2 // (n-2)+2 2+2 1+3 // (n-3)+3 만약 n=4의 조합의 수는 아래와 같다. n=3의 조합의 수에 +1를 한 값들 n=2의 조합의 수에 +2를 한 값들 n=3의.. [백준] 13460 - 구슬 탈출2 Re (java) [백준] 13460 - 구슬 탈출2 (java) 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열 dwc04112.tistory.com static boolean[][][][] visited; 파란구슬 위치에 따른 빨간구슬 위치를 방문처리하여 방문한 좌표는 이동하지 않게 하였다. private static void play() { while(!queue.isEmpty()){ Node temp = queue.remove(); if(temp.count==10) break; visited[temp.redR][temp.redC][temp.bl.. [백준] 13460 - 구슬 탈출2 (java) 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net DP문제집을 풀다가 재미있어 보이는 문제가 있어서 풀기시작했다. 풀면 풀수록 생각할 것이 더 생기는 문제였다. 결국 풀기는 했지만 실행시간이 엄청 오래걸렸다... (이전에 이동한 위치를 또 갈수있게 만들어서 실행 횟수가 엄청 늘어났다) 그래서 이전에 이동한 위치를 visited에 저장해서 다시한번 풀어봐야겠다. 내가 푼 방법 1. 빨강구슬과 파랑구슬은 겹치면 안된다. ( 둘 다 (2,2) 지점으로 간다면 먼저 도착.. [백준] 2294 - 동전 2 (java) 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 문제 주어진 종류의 동전으로 목표금액 k 를 만드는 것이다. 이때 동전의 최소 수를 구한다. ( 위 예제에서는 5원짜리 동전 3개를 사용하여 15를 만들어서 답이 3 ) 첫째 줄 첫번째 숫자 n 은 동전의 종류 k는 목표값이다. 아래에는 n개의 수는 각각의 동전 가치를 나타낸다. (같은 동전이 올 수 있음) 문제 풀이 n개의 코인을 입력받을때 해당 코인의 금액을 dp의 index로 하고 값을 1로했다. dp[입력받은 코인의 값] =.. [백준] 11052 - 카드 구매하기 (java) 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 내용 첫번째 줄에 사야하는 카드의 수 N이 주어진다. 두번째 줄에는 각각 1 ~ N개가 들어있는 카드팩의 금액이 적혀있다. N개의 카드를 가장 비싸게 살 때 해당 금액을 구하는 문제 문제 풀이 DP[ i ]에는 i개의 카드를 가장 비싸게 사는 금액이 저장된다. DP[ 1 ] 에는 본인이 최대값이니 board[ 1 ] 이 저장되고 다음 값부터는 각 DP의 최대값을 찾는다 10 1 1 2 3 5 8 13 21 34 55 DP[2]의 값을 찾으려면 board[2]와 dp.. [백준 java] 1912 - 연속합 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 구해야 하는 것은 연속되는 수의 합중 최대값을 구해야한다. 예제 2와 같이 음수가 들어가도 최대값이 나오는 경우는 있다. 만약 음수를 더해도 연속 수 합의 결과값이 양수라면 ( 3 +4 - 4 +6 +5) 최대값이 된다 dp에는 i 이전 까지의 합과 더해야 할 값( arr[i] ) 중 더 큰값이 저장된다 10 2 1 -4 3 4 -4 6 5 -5 1 다음 예제를 보면 dp[3] = -1 dp[4] = Math.max ( dp[3]+ 3 , 3 ) -> -1 + 3 과 3중.. 이전 1 2 3 4 ··· 9 다음
