본문 바로가기

전체 글69

[백준] 2156번 - 포도주 시식 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 1부터 n번까지 번호가 붙여져 있는 포도주를 1번 -> n번 방향으로 마시는데 연속으로 놓인 잔을 최대 2잔까지만 마실 수 있을 때 마신 포도주 총량의 최대를 구하는 문제이다. 문제 해결을 위한 점화식을 말로 풀어쓰면 다음과 같다. 눈여겨 봐야 하는 조건은 연속으로 놓여 있는 3잔을 모두 마실 수 없다는 조건이다. 따라서 x번째에 놓인 포도주까지 마셨을 때 마신 포도주의 총량의 최대는 다음 i-i, i-ii, ii-i 세 경우 중 하나이다. i) x번째 포도주를 .. 2023. 5. 21.
[백준] 1932번 - 정수 삼각형 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 정수 삼각형의 맨 위층에 놓인 수부터 출발하여 맨 아래층으로 내려올 때, 지나온 경로에 놓인 수를 모두 더한 합이 최대가 되는 경로를 구하는 문제이다. 완전 탐색으로도 풀 수 있지만 문제 특성상 메모제이션을 사용하는 다이나믹프로그래밍을 사용할 수도 있다. 맨 위에서 출발 하여 아래로 내려올 때 현재 위치에서 아래층으로 이동할 수 있는 경로는 두 가지 뿐이다. 현재 위치의 대각선 왼쪽 또는 대각선 오른쪽. 이때 층을 내려가는게 아닌 층을 올라온다고 생각하면 i) 현재 위치의 대각선 왼쪽 경로로 올라왔을 때 합의 최대 ii) 현재 위치의.. 2023. 5. 19.
[백준] 11729번 - 하노이 탑 이동 순서 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 한때 킬링타임용으로 하노이탑 어플을 사용하던 때가 있었기에 반가웠던 문제이다. 하노이탑을 옮기는 기본 원리를 알고 있었기에 문제를 이해하는데에 어려움은 없었지만 막상 코드로 구현하려고 하니 처음에는 어려웠다. 하노이탑의 핵심은 규칙을 지키면서 이동을 최소화 하는 것이다. 문제에서 주어진 원판 5개의 경우로 그 방법을 살펴보자. 요구하는 것은 첫 번째 장대에 쌓여 있는 5개의 원판을 세 번째 장대로 옮겨야 한다. 결과적으로 일단 가장 아래에 있는 크기 .. 2023. 5. 19.
[백준] 2110번 - 공유기 설치 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 이전에 해결한 백준 1654번 랜선 자르기와 유사한 Parametric Search 문제이다. 알고 싶은 것은 가장 인접한 두 공유기 사이의 '최대 거리' 이다. 인접한 두 공유기 사이의 최대 거리 X가 될 수 있는 범위는 다음과 같다. 1 2023. 5. 16.
[백준] 1654번 - 랜선 자르기 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 이전에 해결한 숫자 카드 2 논리를 적용할 수 있는 문제이다. 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제를 풀기에 앞서 Parametric Search에 대한 개념을 간략하게 이해하고 넘어가보자... 2023. 5. 16.
[백준] 10816번 - 숫자 카드 2 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 이전에 해결한 백준 1920번 수 찾기와 유사한 문제이다. 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 이분 탐색으로 특정 숫자의 존재 유무를 확인하는 이전 문제와 동일한 논리를 적용.. 2023. 5. 16.
[백준] 1920번 - 수 찾기 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 이분 탐색의 기본 개념에 대해 이해하기 좋은 문제이다. 이분 탐색이란 어떤 문제를 해결하기 위한 일련의 판단이 YES or NO 판단의 연속인 문제를 말한다. 이 문제의 경우를 예로들어보자. N개의 정수가 주어지고 이 안에 정수 X가 존재하는지 알아보고자 한다. N개의 정수를 일일이 비교하여 X가 존재하는지 확인하는 방법을 사용할 수도 있겠지만 이분 탐색을 적용해볼 수 있다. 이분 탐색을 위해서는 반드시 탐색하는 .. 2023. 5. 16.
[백준] 1629번 - 곱셈 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제가 이렇게 짧은 것은 흔하지 않다. 입력으로 주어지는 자연수 A를 B번 곱한 수를 구하면 되는 간단해 보이는 문제이지만 A, B가 2,147,483,647 이하의 자연수라는 것과 시간 제한이 0.5초에 불과한 것에 유의해야 한다. 입력으로 주어지는 수의 최댓값이 굉장히 커서 자연수이지만 자연수 같지 않은 느낌마저 든다. 어찌됐든, 문제를 푸는데에는 크게 세부분을 주의하면 된다. i) 만약 B가 가질 수 있는 크기의 최댓값이라면, A를 B번 곱할 경우 약 21억번의 연산을 하게 되어 주어진 시간 내에 답을 얻지 못할 것이다... 2023. 5. 12.
[백준] 2630번 - 색종이 만들기 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 분할정복의 기본 개념을 이해하기 좋은 간단한 문제이다. 분할정복(Divide And Conquer)이란 해결하고자 하는 문제를 작은 관점에서 해결하여 최종적으로 원래 해결하고자 했던 문제를 정복하는 방법이다. 이번 문제에서 주어진 조건을 살펴보자. 입력으로 주어지는 전체 정사각형에는 흰색 또는 파란색 두가지 색이 정사각형 모양으로 칠해져 있다. 여기서 '만약 전체 종이가 모두 같은 색으로 칠해져 있지 않다면 가로와 세로로 중간 부분을 .. 2023. 5. 11.

티스토리툴바