넘치게 채우기

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로 책정된다..

https://www.acmicpc.net/problem/14567BOJ - 선수과목문제 유형: 위상 정렬문제 난이도: Gold V시간 제한: 5초메모리 제한: 256MB 문제올해 Z대학 컴퓨터공학부에 새로 입학한 민욱이는 학부에 개설된 모든 전공과목을 듣고 졸업하려는 원대한 목표를 세웠다. 어떤 과목들은 선수과목이 있어 해당되는 모든 과목을 먼저 이수해야만 해당 과목을 이수할 수 있게 되어 있다. 공학인증을 포기할 수 없는 불쌍한 민욱이는 선수과목 조건을 반드시 지켜야만 한다. 민욱이는 선수과목 조건을 지킬 경우 각각의 전공과목을 언제 이수할 수 있는지 궁금해졌다. 계산을 편리하게 하기 위해 아래와 같이 조건을 간소화하여 계산하기로 하였다.한 학기에 들을 수 있는 과목 수에는 제한이 없다.모든 과목은 ..

https://www.acmicpc.net/problem/10711BOJ - 모래성문제 유형: bfs, 그래프문제 난이도: Gold II시간 제한: 1초메모리 제한: 256MB 문제명우와 친구들은 여름방학을 맞이하여 해변가에 놀러가기로 했다. 이번에 여행을 떠난 해수욕장의 이름은 ALPS(Awsome Land & Poor Sea)이다.해변가에서 수영복을 입은 미녀들에게 관심이 많은 원철이와는 달리 명우는 해변가의 모래에 더 관심이 많다. 해변가의 모래는 무한한 것들을 만들 수 있는 가능성을 내포하고 있다. 또한 이렇게 만들어진 작품이 파도에 의해 사라지는 모습은, 마치 자신이 가장 빛날 수 있는 시간을 알고 스스로 아름답게 산화하려는 것으로 보인다. 이런 완벽에 가까운 물품인 모래를 두고서 해수욕이나 헤..

https://www.acmicpc.net/problem/7570BOJ - 줄 세우기문제 유형: 그리디, 다이나믹 프로그래밍문제 난이도: Gold II시간 제한: 1초메모리 제한: 256MB 문제대한 어린이집에 올해 입학한 어린이들이 놀이터에 한 줄로 서있다. 모든 어린이들에게는 입학할 때 주어진 번호가 있고 모두 옷에 번호표를 달고 있다. 그런데 어린이들은 아직 번호 순서대로 줄을 잘 서지 못하므로 선생님이 다음과 같은 방법을 사용해서 번호순서대로 줄을 세우려고 한다.방법: 줄 서있는 어린이 중 한 명을 선택하여 제일 앞이나 제일 뒤로 보낸다.위의 방법을 사용할 때 어린이가 이동해서 빈자리가 생기는 경우에는 빈자리의 뒤에 있는 어린이들이 한 걸음씩 앞으로 걸어와서 빈자리를 메꾼다.예를 들어, 5명의 어..

https://www.acmicpc.net/problem/11735BOJ - 정산소문제 유형: 수학문제 난이도: Gold IV시간 제한: 1초메모리 제한: 256MB 문제가리송과 안드레송은 정산소에서 일하고 있고, 미래를 예측하고자 한다. 둘에게는 큰 n x n 정사각형이 주어진다. 처음에 각 배열의 원소 (x,y)는 x + y 로 채워져있다. (1 ≤ x, y ≤ n).미래 예측을 하는데에 두가지 타입의 쿼리가 들어온다.“R r” ㅡ r행의 모든 값들을 합한 결과를 출력하고, r행을 모두 0으로 바꾼다.“C c”ㅡ c열의 모든 값들을 합한 결과를 출력하고, c열을 모두 0으로 바꾼다.쿼리 결과를 구하는 프로그램을 작성하시오. 입력첫줄에는 배열의 크기 n과 쿼리의 개수 q가 입력된다. (1 ≤ n ≤ 1..

https://www.acmicpc.net/problem/1607BOJ - 원숭이 타워문제 유형: 수학, 다이나믹 프로그래밍난이도: Gold II시간 제한: 1초메모리 제한: 128MB 문제동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그는 자신이 원래 살던 곳으로 돌아가고 싶었지만 너무 멀어서 갈 수 없었다. 그래서 그는 자신이 살던 곳의 전통방식으로 지어진 탑을 간절히 생각하며 슬픔을 달래기로 했다. 그 탑의 이름은 원숭이 타워!!원숭이 타워는 원숭이들이 만든 것이라고는 하지만 원숭이들의 창의력이 부족하여 실제로는 하노이지방의 하노이타워를 응용하여 만든 탑이다. 이제 그 탑을 살펴보자.위의 그림에 잘 나타나있다. 원숭이 타워가 하노이타워와 다른 점은 기둥을 네 개를 쓴다는 점이다. 이..