[java] 백준 2206 (벽 부수고 이동하기) Gold 4

Problem : https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net Approach 조건이 달려있는 경로 최소비용 문제이다. 필자는 BFS를 사용했다. 경우의 수를 따지기 전에, 현재 위치에서 벽을 부시고 왔는지에 대한 brokenWall[x][y] 배열이 필요하다. brokenWall[x][y] 의 값이 2이면, 해당 (x, y)를 아직 방문하지 않았다는 뜻이고, 1이라면, 해당 (x, y)를 방문했는데 방문하기전에 경..

→2020.12.30

Algorithm/Baekjoon Online Judge

[java] 백준 7569 (토마토2) Silver 1

Problem : https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net Approach 백준 7576번 토마토 문제와 같은 문제이지만, 3차원 배열로 구성된 문제이다. 7576번 문제의 풀이는 밑의 링크에 있다. 2020/12/30 - [Algorithm/Baekjoon Online Judge] - [java] 백준 7576 (토마토1) Silver 1 [java] 백준 7576 (토마토1) Silver 1 Problem : ..

→2020.12.30

Algorithm/Baekjoon Online Judge

[java] 백준 7576 (토마토1) Silver 1

Problem : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net Approach 시작점이 여러개인 최단경로 문제이다. 문제에서 배열의 요소가 1인 모든 곳이 시작점이다. (따라서 요소가 1인 모든 좌표를 큐에 넣고 BFS를 수행한다.) 벽이 -1 로 막혀있지 않고, 범위를 벗어나지 않으며, 방문하지 않았다면, 방문하면서 직전 위치의 값 + 1을 방문하는 곳에 저장한다. BFS가 완전히 모두 수행된 후, 최단경로 배열을 검사하여..

→2020.12.30

Algorithm/Baekjoon Online Judge

[java] 백준 10942 (팰린드롬) Gold 2

Problem : https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net Approach 팰린드롬은 주어진 문자열을 거꾸로해도 원래의 문자열과 같은 경우를 말한다. 일반적으로 팰린드롬은 DP 문제가 아니지만, 하나의 문자열으로 범위를 나누어 팰린드롬인지를 검사할 때에는 DP를 써서 상태를 저장한다면 시간을 조금 단축시킬 수 있다. 일단 범위 (s, e) 가 팰린드롬이라면, 시작인덱스와 끝인덱스에 같은 수를 더하고 뺀 범위는 항상 팰린드롬이다. 예를 들어, (s, e) 가 팰린드롬이면, (s..

→2020.12.28

Algorithm/Baekjoon Online Judge

[java] 백준 7579 (앱) Gold 3

Problem : https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net Approach DP 문제로 냅색(KnapSack) 문제와 유사하다. N cost로 최대 몇 M size를 비활성화 할 수 있는지를 고민해서 풀어야 한다. DP[i][j] = i개의 앱이 있을 때, j cost로 비활성화 할 수 있는 최대 사이즈이다. 그런 후, X개 앱이 있을 때, Y size를 처음으로 넘기는 cost를 찾으면 된다. Code import java.io.*; impo..

→2020.12.28

Algorithm/Baekjoon Online Judge

[java] 백준 1520 (내리막 길) Gold 4

Problem : https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net Approach 최단거리 문제가 아니므로 미로문제 처럼 갈 수 있는 모든 곳을 방문해 봐야 한다. DP[i][j] = (i, j) 위치에서 최종 목적지까지 갈 수 있는 방법의 수라고 정의한다. DP[i][j] == 0 은 방문했음을 표시한 것이고, -1은 도달할 수 없는 곳이다. 현재 위치를 방문 했음을 표시하고, 상하좌우로 갈 수있는지 검사하여 갈 수 있다면 재귀를 돌리면서 리턴 값..

→2020.12.28

Algorithm/Baekjoon Online Judge

[java] 백준 2293 (동전 1) Silver 1

Problem : https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net Approach DP 문제이다. 입력되는 동전의 가치가 오름차순으로 주어진다는 말이 없어 동전의 가치를 저장한 배열을 오름차순으로 정렬시킨 후, 다음과 같은 규칙을 이용하여 문제를 풀어나가면 된다. 코인의 가치가 a, b, c 일 때, x를 만드는 방법의 수는 x - a원 에서 a원을 더하여 만드는 법(1), x - b원에서 b원을 더하여 만드는 법(2), x - c 원에서 c원을..

→2020.12.27

Algorithm/Baekjoon Online Judge

[java] 백준 11049 (행렬 곱셈 순서) Gold 3

Problem : https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net Approach DP 문제로 행렬의 곱셈규칙을 알아야 한다. A x B 행렬, B X C 행렬을 곱한다고 하였을 떄, 필요한 곱셈연산 수는 A x B x C번이며, 곱셈으로 만들어진 행렬은 A x C 크기의 행렬이다. 그리고 이 행렬과 C x D 행렬을 곱한다고 하였을 때, 필요한 곱셈연산 수는 A x C x D 이다. 그리고 만들어진 행렬의 크기는 A x D 이다...

→2020.12.27

Algorithm/Baekjoon Online Judge

[java] 백준 11066 (파일 합치기) Gold 3

Problem : https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net Approach DP를 이용한 문제로, DP[i][j] = i ~ j까지의 파일을 합치는 최소 비용 이라고 정의하고 문제에 접근한다. 주어진 파일의 개수가 1개라면, 그 파일의 크기를 return 한다. 주어진 파일의 개수가 2개라면, 두 개의 파일 크기를 합친 값을 return 한다. 주어진 파일의 개수가 3개 이상이라면, DP[i][j] = DP[i][k] + DP[..

→2020.12.27

Algorithm/Baekjoon Online Judge

[java] 백준 12865 (평범한 배낭) Gold 5

Problem : https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net Approach 대표적인 DP 문제인 KnapSack Problem이다. DP[i][j] 는 j만큼의 무게를 견딜 수 있는 가방에 처음 i개의 물건들로 담을 수 있는 최대 가치를 말한다. - i번째 물건의 무게 weight 가 현재 넣을 수 있는 무게 j보다 크다면 DP[i][j] = DP[i - 1][j]이다. ..

→2020.12.24

티스토리툴바