본문 바로가기
728x90

전체 글

[C++]백준 14719번: 빗물 문제 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 문제이해 첫 번째 줄에 H(세로의 길이)와 W(가로의 길이)를 입력한다. 두 번째 줄에 W개의 블록이 쌓인 높이를 입력한다. 고이게 되는 빗물의 총량을 출력한다. 가로를 기준으로 N번째의 위치에 고이게 되는 빗물의 높이를 구하기 위해서는 N번째 위치를 기준으로 왼쪽과 오른쪽에 가장 높게 쌓인 부분을 구해야 합니다. 이후 왼쪽의 가장 높게 쌓인 부분과 오른쪽의 가장 높게 쌓인.. 더보기
[C++]백준 2468번: 안전 영역 문제 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 문제이해 첫째 줄에 N을 입력한다. 두번째 줄부터 NxN 크기의 영역의 정보를 입력한다. 안전한 영역의 최대 개수를 출력한다. 구현하는게 생각보다 간단한 문제입니다. 높이를 정하고 높이에 따라 잠기지 않는 영역을 발견하면 그 옆에 붙어있는 잠기지 않는 영역까지 구하기 위해 너비우선탐색(BFS)를 사용하여 구역을 찾고 구역의 개수를 구하면 됩니다. 물에 잠기지 않는 안전한 영역의 최대 개수를 구하기 .. 더보기
[C++]백준 1715번: 카드 정렬하기 문제 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제이해 첫째 줄에 N이 주어집니다. 두 번째 줄부터 N개만큼의 카드 묶음을 입력합니다. 최소 비교 횟수를 출력합니다. 이 문제에서 주목해야 하는 부분은 바로 숫자 카드 묶음이 한 개만 남기 전까지 모든 카드를 묶는다는 것입니다. 카드 묶음과 카드 묶음을 묶어 새로운 카드 묶음을 만들고 이 새로운 카드 묶음은 다시 다른 카드묶음과 합쳐지게 됩니다. 간단하게 말하자면 카드 묶음이.. 더보기
[C++]백준 5014번: 스타트링크 문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제이해 첫째 줄에 F, S, G, U, D를 입력한다. 강호가 S층에서 G층으로 가기 위해서 눌러야 하는 버튼 수의 최솟값을 출력한다. G층으로 갈 수 없다면 "use the stairs"를 출력한다. S층에서 G층으로 가는 최단 거리를 찾는 문제로 너비 우선 탐색(BFS)를 이용하여 풀어야 되는 문제이다. 큐(queue)에 강호가 처음에 있는 층인 S층을 넣고 시작한다. 이후 큐(queue)의 fro.. 더보기
[C++]백준 1463번: 1로 만들기 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제이해 첫째 줄에 N을 입력합니다. 연산 횟수의 최솟값을 출력합니다. 이 문제는 다이나믹 프로그래밍을 이용해야 합니다. 배열을 통해 설명해 보겠습니다. dp [i]는 i를 1로 만드는데 걸리는 연산 횟수의 최솟값을 의미합니다. dp [2]와 dp [3]은 당연히 1입니다. dp [4]의 경우 dp [2]에 1을 더한 값 또는 dp [3]에 1을 더한 값인 2입니다. dp [5]는 5 - 1 = 4, 4 - 1 = 3, 3 / 3 = 1 또는 5 - 1 = 4, 4 / 2 = 2, 2 / 2 = 1 이러한.. 더보기
[C++]백준 11727번: 2xn 타일링 2 문제 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 문제이해 째 줄에 n을 입력합니다. 2xn 크기의 직사각형을 채우는 방법을 10007로 나눈 값을 출력합니다. 이 문제는 다이나믹 프로그래밍을 사용하는 문제입니다. 사용할 수 있는 블록은 2x1로 된 가로블록, 1x2로 된 세로 블록, 2x2로 된 정사각형 블록으로 총 3개가 있습니다. 점화식을 찾기 위해 우선 배열을 통해 설명해 보겠습니다. 2xi 크기의 직사각형을 채우는 방법을 의미합니다. dp [1]은 세로블록 한 .. 더보기
[C++]백준 11726번: 2xn 타일링 문제 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제이해 첫째 줄에 n을 입력합니다. 정답이 되는 방법의 수를 10007로 나눈 나머지를 출력합니다. 이 문제는 다이나믹 프로그래밍을 사용해야합니다. 방법의 수를 찾기 위해서는 우선 점화식부터 찾아야합니다. 이를 배열로써 설명해보겠습니다. dp[i]는 2xi 크기의 직사각형을 채우는 방법의 수를 의미합니다. dp[1]은 1, dp[2]는 2, dp[3]은 3이라고 할 수 있습니다. 그렇다면 dp[4]의 값은 얼마.. 더보기
[C++]백준 11286번: 절댓값 힙 문제 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제이해 첫째 줄에 연산의 개수(N)를 입력합니다. N개의 줄에 대해 연산의 정보(x)를 입력합니다. 입력에서 0이 입력된 수만큼 답을 출력합니다. 절댓값을 기준으로 정렬된 힙을 만들기 위해서는 당연히 절댓값을 기준으로 정렬한 우선순위 큐(priority_queue)를 사용하여야 합니다. 주의해야 할 점이 있다면 절댓값이 같고 부호가 다른 수에 대해서는 음수가 우선순위가.. 더보기
LIST

티스토리툴바