넘치게 채우기

https://www.acmicpc.net/problem/24419BOJ - 알고리즘 수업 - 행렬 경로 문제 2문제 유형: 조합론, 수학문제 난이도: Silver II시간 제한: 1초메모리 제한: 512MB 문제오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.양의 정수로 이루어진 n × n 행렬 m이 주어진다. 행렬의 왼쪽 위에서 시작해 한 칸씩 이동해 오른쪽 아래까지 도달한다. 이 과정에서 방문한 칸에 있는 수들을 더한 값이 이 경로의 합이다. 이동 규칙은 다음과 같다.오른쪽이나 아래쪽으로만 이동할 수 있다.왼쪽, 위쪽, 대각선 이동은 허용하지 않는다.행렬의 원소 (1, 1)에서 (n, n)으로 이동하는 모든 경로의 점수 ..

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)이 발생했다. 키위새는 이제 매일 노점에 들러 가지 디저..