넘치게 채우기

https://www.acmicpc.net/problem/2982BOJ - 국왕의 방문문제 유형: 다익스트라, 그래프문제 난이도: Gold II시간 제한: 1초메모리 제한: 128MB 문제지난주에 상그니 아라비아의 국왕 고둘라 창지즈 영사우드가 한국에 도착했다. 고둘라는 매우 중요한 사람이다. 따라서, 경찰은 그가 타고 있는 차량이 길에 진입했을 때, 그가 길에 있는 동안에 다른 차량이 들어올 수 없게 통제할 것이다. 하지만, 그가 진입하기 전부터 길에 있던 차량은 계속 있을 수 있다.상근이는 오토바이 소년 승환이의 뒤를 이어 근처에서 피자를 트럭으로 배달하는 사람이다. 상근이는 교통 통제 때문에 배달을 정시에 하지 못해서 짤릴뻔했다.이미 고둘라 창지즈 영사우드는 상그니 아라비아로 돌아갔다. 하지만 상근..

https://www.acmicpc.net/problem/30686BOJ - 과제 제출하기문제 유형: 그리디, 브루트 포스문제 난이도: Gold V시간 제한: 1초메모리 제한: 1024MB 문제성현이가 배우는 과목은 N개의 지식을 포함한다. 지식은 1부터 N까지의 정수로 나타낼 수 있다.성현이는 M개의 모든 문제를 풀어서 제출해야 한다. 한 문제를 푸는 데는 하루가 걸리고, 성현이는 문제를 푸는 순서를 마음대로 정할 수 있다. 따라서 성현이는 1일, 2일, ..., M일에 문제를 각각 하나씩 풀어야 한다.각 문제를 풀기 위해서는 각 문제가 요구하는 지식이 필요하다. i번째 문제를 해결하기 위해서는 a_{i,1}번, a_{i,2}번, ..., a_{i,k_i}번의 총 k_i개의 지식이 필요하다.또한 지식은..

https://www.acmicpc.net/problem/13904BOJ - 과제문제 유형: 그리디, 우선순위 큐, 정렬문제 난이도: Gold III시간 제한: 1초메모리 제한: 256MB 문제웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오. 입력첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는..

https://www.acmicpc.net/problem/33496BOJ - 미술 수업문제 유형: 수학, 기하학, 정렬, 이분 탐색, 집합, 스위핑문제 난이도: Gold IV시간 제한: 1초메모리 제한: 1024MB 문제창하는 재작년 미술 수업 최종 프로젝트로 다음과 같은 그림을 그린 덕분에 과목우수상을 받았다.비어있는 2차원 좌표평면을 준비한다. N개의 점 (X_1, Y_1), (X_2, Y_2), ..., (X_N, Y_N)을 정한다. 단, Y_i > 0이다. x축을 나타내는 직선을 그린다. i = 1, 2, \cdots, N에 대해 점 (X_i, Y_i)을 지나고, 기울기가 각각 1과 -1인 두 개의 직선을 그린다. 단, x축 아래의 부분은 그리지 않는다.아래는 창하의 그림의 예시를 나타낸 것이다...

https://www.acmicpc.net/problem/15979BOJ - 스승님문제 유형: 수학, 애드혹, 정수론, 유클리드 호제법문제 난이도: Silver II시간 제한: 1초메모리 제한: 512MB 문제현욱은 옛날 자신에게 알고리즘을 가르쳐 준 스승님이 어느 신비로운 밀림 속 나무 아래에서 수행 중이라는 사실을 전해 들었다.이 무한한 넓이의 밀림에는 모든 격자점(x, y 좌표가 모두 정수인 위치)마다 완전히 똑같은 모양의 나무가 한 그루씩 심어져 있고, 현욱의 스승은 그 중 (M,N) 좌표의 나무 아래에서 수행을 하고 있다.이 밀림에는 또 다른 특징이 있는데, 어떤 나무 아래에서 볼 수 있는 다른 나무로 순간이동을 할 수 있다는 것이다. 어떤 나무 아래에서 다른 나무를 보려면, 그 두 나무의 좌표..

https://www.acmicpc.net/problem/12911BOJ - 좋아하는 배열문제 유형: 수학, 정수론, 다이나믹 프로그래밍문제 난이도: Gold II시간 제한: 2초메모리 제한: 512MB 문제성관이는 다음과 같은 성질을 만족하는 배열을 좋아한다.배열의 길이는 N이다.배열에 채워져있는 수는 1보다 크거나 같고, K보다 작거나 같은 자연수이다.배열에서 연속한 수가 A와 B일 때, A 예를 들어, N = 4, K = 7인 경우에 [1, 7, 7, 2]는 성관이가 좋아하는 배열이다. 모든 연속한 수가 1 N과 K가 주어졌을 때, 성관이가 좋아하는 배열의 경우의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000) 출력첫째 줄..

https://www.acmicpc.net/problem/27945BOJ - 슬슬 가지를 먹지 않으면 죽는다문제 유형: 그래프, MST(최소 신장 트리), 분리 집합, 유니온 파인드문제 난이도: Gold III시간 제한: 1초메모리 제한: 1024MB 문제키위새는 가지와 사랑에 빠지면서 가지로 맛있는 요리를 하기 위해 1번부터 N번까지의 번호가 붙은 N개의 요리 학원에 다니기 시작했다.각 요리 학원 사이에는 총 M개의 양방향 길이 있고, i번째 길에는 정확히 ti일에만 문을 여는 가지 디저트 노점이 있다. (ti는 모두 다르다.) 아직 가지 요리를 배우는 중인 키위새는 직접 가지 요리를 해 먹지는 못하다 보니 가지 부족증(hypomelitzemia)이 발생했다. 키위새는 이제 매일 노점에 들러 가지 디저..

https://www.acmicpc.net/problem/31455BOJ - 쿠키 자르기문제 유형: 재귀, 분할 정복문제 난이도: Silver I시간 제한: 1초메모리 제한: 512MB 문제Albert는 2K×2K 크기의 쿠키를 구워 각 칸에 0-9 사이의 숫자를 적어두었다 - 이 문제에서 편의상 r 행 c열에 적힌 숫자는 A[r,c]로 나타내자 (0≤A[r,c]≤9).예를 들어 아래 그림은 K=2 이고 A=[[1,2,3,4],[2,3,4,5],[3,4,5,6],[0,9,8,7]] 인 쿠키의 모습을 보여준다.구워진 쿠키를 감상하던 Bob은 Albert에게 아래와 같은 놀이를 제안했다.크기가 N×N인 쿠키를 N/2×N/2 크기로 4등분 하여 그 중 한 조각을 둘이 나눠 먹는다.우선 아래 그림의 좌측과 같이..

https://www.acmicpc.net/problem/1106BOJ - 호텔문제 유형: 다이나믹 프로그래밍, 배낭 문제문제 난이도: Gold IV시간 제한: 2초메모리 제한: 128MB 문제세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지..

https://www.acmicpc.net/problem/1513BOJ - 경로 찾기문제 유형: 다이나믹 프로그래밍문제 난이도: Gold II시간 제한: 2초메모리 제한: 128MB 문제세준이는 크기가 N*M인 직사각형 도시에 살고 있다. 또, 세준이의 집은 (1, 1)에 있고, 학원은 (N, M)에 있고, 오락실이 C개 있다.세준이의 현재 위치가 (r, c) 일 때, (r+1, c) 또는 (r, c+1)로만 이동할 수 있다. 오락실을 방문할 때는 규칙이 하나 있는데, 오락실 번호가 증가하는 순서대로 가야한다는 것이다. 2번 오락실을 먼저 가고, 그 후에 1번 오락실을 가면 안 되고, 2번 오락실을 가려면, 그 전에 아무 오락실도 가지 않거나, 1번 오락실을 방문했을 때만 가능하다.세준이는 오락실을 K번..