백준 실버문제(56)
-
백준 온라인 저지, 그리디 / 1246번: 온라인판매 (파이썬 / 백준 실버문제)
문제 주소: https://www.acmicpc.net/problem/1246 문제 경래는 닭을 기르는데 올 겨울 달걀 풍년으로 함박 웃음을 짓고 있다. 그리고 이 달걀을 영양란으로 둔갑하여 옥션에 판매하려한다. 경래는 총 N개의 달걀이 있고, 그의 잠재적인 고객은 총 M명이다. 그리고 각각의 i번째 고객은 각자 달걀 하나를 Pi 가격 이하로 살 수 있다고 밝혔다. 경래는 영양란이라 속인 죄책감에 한 고객에게 두 개 이상의 달걀은 팔지 않기로 하였다. 하지만 위의 규칙 하에 수익은 최대로 올리고 싶기에 얼마로 팔지 고민하고 있다. 즉, A가격에 달걀을 판다고 하면 Pi가 A가격보다 크거나 같은 모든 고객은 달걀을 산다는 뜻이다. (물론 달걀 총 수량을 초과하여 팔 수 는 없다) 문제는 이러한 경래를 도와..
2022.05.18 -
백준 온라인 저지, 구현 / 9613번: GCD합 (파이썬 / 백준 실버문제)
문제 주소: https://www.acmicpc.net/problem/9613 문제 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다. 출력 각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다. 제한 예제 입력 1 복사 3 4 10 20 30 40 3 7 5 12 3 125 15 25 예제 출력 1 복사 70 3 35 힌트 W3sicHJvYmxlbV9pZCI6Ijk2MTM..
2022.05.16 -
백준 온라인 저지, 구현 / 1292번: 쉽게푸는문제 (파이썬 / 백준 실버문제)
문제 주소: https://www.acmicpc.net/problem/1292 문제 동호는 내년에 초등학교를 입학한다. 그래서 동호 어머니는 수학 선행 학습을 위해 쉽게 푸는 문제를 동호에게 주었다. 이 문제는 다음과 같다. 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 1 2 2 3 3 3 4 4 4 4 5 .. 이러한 수열을 만들고 어느 일정한 구간을 주면 그 구간의 합을 구하는 것이다. 하지만 동호는 현재 더 어려운 문제를 푸느라 바쁘기에 우리가 동호를 도와주자. 입력 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. 출력 첫 줄에 구간에 속하는 숫자의 합을 출력한다. 제한 ..
2022.05.16 -
백준 온라인 저지, 이진탐색 / 16401번: 과자나눠주기 (파이썬 / 백준 실버문제)
문제 주소: https://www.acmicpc.net/problem/16401 문제 명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다. 조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다. 그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다. M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라. 단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다. ..
2022.05.13 -
백준 온라인 저지, BFS / 16948번: 데스나이트 (파이썬 / 백준 실버문제)
문제 주소: https://www.acmicpc.net/problem/16948 문제 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다. 데스 나이트는 체스판 밖으로 벗어날 수 없다. 입력 첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r1, c1, r2, c2가..
2022.05.13 -
백준 온라인 저지, 그리디 / 21600번: 계단 (파이썬 / 백준 실버문제)
문제 주소: https://www.acmicpc.net/problem/21600 문제 자료의 분포를 아래의 그림과 같이 나타낸 그래프를 히스토그램이라고 합니다. 당신은 히스토그램 영역에서 가장 큰 계단을 찾으려고 합니다. 계단은 아래 조건을 만족하는 영역을 말합니다. 계단의 ‘길이’는 계단에 포함된 히스토그램의 열의 수를 나타냅니다. 계단의 길이가 $L$이라고 할 때, 왼쪽에서 $i$번째 열은 높이가 $i$입니다. 즉, 맨 왼쪽 열의 높이는 1, 그 다음 열의 높이는 2이고, 맨 오른쪽 열의 높이는 $L$입니다. 히스토그램 영역이 계단을 포함하면 되기 때문에, 히스토그램의 높이가 계단의 높이 이상이기만 하면 되고, 정확히 같을 필요는 없습니다. 위 히스토그램에서 가장 큰 계단은 아래와 같습니다. 가장 큰..
2022.05.13