넘치게 채우기

https://www.acmicpc.net/problem/10750BOJ - Censoring문제 유형: 문자열 처리, 스택문제 난이도: Gold IV시간 제한: 1초메모리 제한: 256MB 문제Farmer John has purchased a subscription to Good Hooveskeeping magazine for his cows, so they have plenty of material to read while waiting around in the barn during milking sessions. Unfortunately, the latest issue contains a rather inappropriate article on how to cook the perfect steak,..

https://www.acmicpc.net/problem/6209BOJ - 제자리 멀리뛰기문제 유형: 이진 탐색(parametric search), 그리디문제 난이도: Gold II시간 제한: 1초메모리 제한: 128MB 문제GSHS에서는 체력측정에서 제자리 멀리뛰기가 가장 중요하다. GSHS의 체육선생님께서는 학생들의 제자리 멀리뛰기 실력을 키워주게 하기 위해서 특수 훈련을 준비중이다.특수 훈련장소는 GSHS특수 트레이닝 센터로 이 곳은 끓는 용암으로 가득 차 있다. 체육선생님께서는 이 용암으로 가득찬 방의 가운데 있는 돌섬에 학생들을 가두고 학생들이 탈출해 나오기를 기대하고 있다. 탈출할 수 있는 방법은 단 한가지 이다. 돌섬에서 탈출구까지 띄엄 띄엄 존재하는 작은 돌섬들로 점프하여 탈출구까지 가는 ..

https://www.acmicpc.net/problem/1188BOJ - 음식 평론가문제 유형: 수학, 정수론, 유클리드 호제법문제 난이도: Gold IV시간 제한: 1초메모리 제한: 128MB 문제선영이의 직업은 소시지 요리사이다. 소시지를 팔기 전에 음식 평론가 M명을 모아서 맛을 테스트해보려고 한다.선영이는 동일한 소시지를 총 N개를 준비했다. 이 소시지를 모든 평론가들이 같은 양을 받게 소시지를 자르려고 한다. 이때, 소시지를 자르는 횟수를 최소로 하려고 한다.예를 들어, 소시지가 2개, 평론가가 6명있는 경우를 생각해보자. 이때, 각 소시지를 세 조각으로 만든 다음, 각 평론가에게 한 조각씩 주면 된다. 이 경우에 소시지는 총 네 번 자르게 된다. 다른 경우로 소시지가 3개, 평론가가 4명 있..

https://www.acmicpc.net/problem/1153BOJ - 네 개의 소수문제 유형: 수학, 정수론, 소수 판별, 에라토스테네스의 체문제 난이도: Gold III시간 제한: 2초메모리 제한: 128MB 문제임의의 자연수가 주어지면, 이를 네 개의 소수의 합으로 분해하는 프로그램을 작성하시오. 예를 들어 38 = 5 + 7 + 13 + 13이 된다. 입력첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력첫째 줄에 네 개의 소수를 빈 칸을 사이에 두고 순서대로 출력한다. 불가능한 경우는 -1을 출력한다. 풀이우선, 에라토스테네스의 체를 이용해서 소수들을 걸러준다. 골드바흐 추측으로 풀 수 있다고 한다. 골드바흐 추측은 2보다 큰 모든 짝수는 두 소수의 합으로 표현될 수 있..

https://www.acmicpc.net/problem/31963BOJ - 두 배문제 유형: 수학, 그리디문제 난이도: Gold III시간 제한: 1초메모리 제한: 1024MB 문제길이 N인 양의 정수열 A1,…,AN이 주어진다. 이 수열을 오름차순으로 만들려 한다. 수열 A1,…,AN이 오름차순이라는 것은, 각 i (1≤i≤N−1)에 대해 Ai≤Ai+1이라는 것이다.수열 A를 오름차순으로 만들기 위해, 수열 A에 다음 연산을 몇 번이든 반복해서 적용할 수 있다.어떤 i (1≤i≤N)에 대해 Ai에 2를 곱한다.연산을 최소 횟수로 적용해서 A를 오름차순으로 만들고 싶다. 이때, 최소 횟수를 구하라. 입력첫 번째 줄에 N이 주어진다.두 번째 줄에 A1,…,AN이 주어진다. 주어지는 모든 수는 정수이다. ..

https://www.acmicpc.net/problem/9991BOJ - Auto-Complete문제 유형: 문자열 처리, 정렬, 이진탐색문제 난이도: Gold IV시간 제한: 1초메모리 제한: 128MB 문제Bessie the cow has a new cell phone and enjoys sending text messages, although she keeps making spelling errors since she has trouble typing on such a small screen with her large hooves. Farmer John has agreed to help her by writing an auto-completion app that takes a partial wor..

https://www.acmicpc.net/problem/1082BOJ - 방 번호문제 유형: 다이나믹 프로그래밍, 그리디문제 난이도: Gold III시간 제한: 1초메모리 제한: 128MB 문제스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이다.문방구에서 파는 숫자는 0부터 N-1까지이고, 각 숫자 i의 가격은 Pi이다. 문방구에서는 같은 숫자를 여러 개 구매할 수 있고, 문방구는 매우 많은 재고를 보유하고 있기 때문에, 항상 원하는 만큼 숫자를 구매할 수 있다. 방 번호가 0이 아니라면 0으로 시작할 수 없다.예를 들어, N = 3, M = 21, P0 = 6, P1 = 7, P2 =..

https://www.acmicpc.net/problem/3066BOJ - 브리징 시그널문제 유형: 이진 탐색, LIS(Longest Increasing Subsequence)난이도: Gold II시간 제한: 1초메모리 제한: 128MB 문제ACM(Advanced Chip Manufacture)이라는 회사의 수석 칩(chip) 설계자인 한승이는 고민에 빠져있다. 경로 설계자들의 잘못으로 두 개의 블록의 포트를 연결하는 칩 위의 시그널들이 서로 교차하게 만들어졌다. 이 시점에서 경로 설계를 다시 하는 것은 비용이 너무 많이든다. 그 대신 엔지이너들은 교차하는 시그널들을 브리징 하기로 했다. 브리징은 시그널이 서로 교차하는 경우 하나의 시그널이 다른 시그널과 접촉하지 않도록 수직으로 띄우는 작업이다. 하지만..

https://www.acmicpc.net/problem/25823BOJ - 조합의 합의 합문제 유형: 조합, 수학, 정수론문제 난이도: Gold I시간 제한: 1초메모리 제한: 512MB 문제양의 정수 M이 주어질 때 다음 식의 값을 구하는 프로그램을 작성하시오. ∑n=3M∑k=0n(nk)2이때 (nk)는 이항계수를 의미한다.단, 답이 너무 커질 수 있으니 10^9+7로 나눈 나머지를 출력한다. 입력첫째 줄에 정수 M이 주어진다. (3≤M≤200000) 출력첫째 줄에 문제에서 주어진 식의 값을 10^9+7로 나눈 나머지를 출력한다. 풀이 이다.독립되게 n개에서 k개뽑기의 합은 2n개에서 n개뽑기와 같다.첫 조합에서 k개를 뽑고, 그 다음 두 번째 조합에서 n-k개를 선택한다고 보면 된다. 이제, 페르마..

https://www.acmicpc.net/problem/23845BOJ - 마트료시카문제 유형: 히스토그램, 그리디, 모노토닉 스택문제 난이도: Gold III시간 제한: 1초메모리 제한: 1024MB 문제 인형 수집가 하령이에게는 N개의 속이 비어있는 인형이 있다. 각각의 인형은 크기는 Xi이다.인형의 속은 비어있기 때문에 그 안에 또 다른 인형을 넣을 수 있고, 크기가 서로 다른 인형들을 조합해서 마트료시카를 만들 수 있다. 정확히는 가장 큰 인형의 크기를 Q, 가장 작은 인형의 크기를 W, 인형의 개수를 T라고 할 때, (Q - W + 1 = T)를 만족하는 인형의 집합을 마트료시카라고 하자. 마트료시카는 1개의 인형으로 구성될 수도 있음에 유의하라.하나의 마트료시카의 가격은 Q × T로 책정된다..