넘치게 채우기

https://www.acmicpc.net/problem/22981BOJ - 휴먼 파이프라인문제 유형: 정렬, 그리디문제 난이도: Gold V시간 제한: 1.5초메모리 제한: 1024MB 문제오늘은 중요한 날이다. SUAPC가 있는 날이기 때문이다.이렇게 중요한 날이지만 안타깝게도 일을 해야 한다. 오늘 해야 할 일은 상자 K개를 적절한 곳으로 옮겨야 하는 일이다.상자 K개는 너무 많아서 아무래도 혼자서 전부 나를 수는 없기 때문에, N명의 SUAPC 참가자들이 상자를 나르기 위해 모여 있다. N명 모두가 일을 최대한 빠르게 마치고 SUAPC에 참가하고 싶어한다.참가자들은 두 팀으로 나눠져서 작업을 진행하기로 했다. 두 팀이 같은 수의 상자를 옮길 필요는 없다. 두 팀 모두 적어도 한 명은 포함되어야 한..

https://www.acmicpc.net/problem/23748BOJ - 방문 판매문제 유형: 다이나믹 프로그래밍, 배낭 문제문제 난이도: Gold II시간 제한: 1초메모리 제한: 1024MB 문제SG그룹은 이번에 획기적인 제품 X, Y를 출시했다. SG그룹의 영업 부서에서 외판원으로 일하는 판매왕 레오는 이 두 제품을 주어진 각 할당량 X, Y만큼 N명의 고객의 집을 모두 방문하여 팔아야 한다. 고객마다 1번부터 N번까지 번호가 주어지고, i번 고객의 집에 방문하여 판매에 성공했을 때 팔 수 있는 제품 X, Y의 양이 각각 x_i, y_i로 주어진다. 그러나 어떤 고객은 방문하더라도 제품 구매를 거절하여 판매에 실패할 수 있다.방문 판매를 할 때는 영업 부서에서 정한 매뉴얼에 따라 1번 고객부터 ..

https://www.acmicpc.net/problem/33693BOJ - C)문제 유형: 그리디, 문자열문제 난이도: Gold IV시간 제한: 1초메모리 제한: 1024MB 문제UDPC만을 손꼽아 기다리던 포닉스는 어느새 어디를 봐도 알파벳 U, D, P, C가 보이는 수준에 이르렀다. 그중에서도, 알파벳 C, U와 괄호 ( , )는 굉장히 유사한 모양을 띠기 때문에 구별하기가 매우 힘들어졌다.다행인 점은, 알파벳 C와 U를 돌려 마치 괄호처럼 사용할 수 있다는 점이다. C는 그 모습 그대로 여는 괄호 ( 로 사용하거나, 어느 방향으로든 90도씩 두 번을 돌려 닫는 괄호 ) 로 사용할 수 있다. U는 시계 방향으로 90도를 회전하면 여는 괄호 ( , 반시계 방향으로 90도를 회전하면 닫는 괄호 ) 로..

https://www.acmicpc.net/problem/4563BOJ - 피타고라스의 복수문제 유형: 정수론, 수학, 기하학문제 난이도: Gold V시간 제한: 1초메모리 제한: 128MB 문제피타고라스의 정리는 직각삼각형의 세 변의 관계를 나타내는 정리이다. 빗변의 길이를 C, 다른 두 변의 길이를 A, B라고 한다면 다음과 같은 식으로 쓸 수 있다.A^2 + B^2 = C^2세 변의 길이가 모두 자연수인 직각삼각형 중에 가장 유명한 삼각형은 아래와 같다.A = 12인 경우에는 다음과 같이 두 개의 직사각형을 찾을 수 있다.A가 주어졌을 때, 빗변의 길이 C가 자연수인 직각삼각형을 만드는 자연수 B (B > A)는 몇 개가 있을까? 입력입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이..

https://www.acmicpc.net/problem/30704BOJ - 정사각형 연결문제 유형: 수학, 애드 혹문제 난이도: Gold V시간 제한: 1초메모리 제한: 1024MB 문제한 변의 길이가 1인, 모양과 크기가 같은 정사각형 모양의 타일이 N장 주어진다. 그리고 한 변의 길이가 1인 정사각형들로 이루어진 격자가 그려진 바닥이 있다. 이 바닥에 타일들을 이어 붙여 하나의 도형을 만들자.타일은 격자판의 각 칸에 맞춰서만 붙일 수 있으며, 타일끼리 겹치거나 포갤 수 없다. 또 모든 타일은 서로 연결되어 있어야 한다.정사각형 타일의 장수가 주어지면, 이들을 위에서 설명한 규칙에 맞게 이어 붙여 만들 수 있는 도형 둘레의 최솟값을 구하여라. 하나의 입력에서 T개의 테스트 케이스를 해결해야 한다. 입..

https://www.acmicpc.net/problem/12906BOJ - 새로운 하노이 탑문제 유형: BFS, 해시, 문자열 처리문제 난이도: Gold III시간 제한: 3초메모리 제한: 512MB 문제오늘은 새로운 하노이 탑 게임을 해보려고 한다. 이 게임의 규칙은 다음과 같다.막대는 총 세 가지 종류가 있다. 막대 A, 막대 B, 막대 C게임이 시작될 때, 각각의 막대에는 0개 또는 그 이상의 원판이 놓여져 있다.모든 원판의 크기는 같으며, 원판의 종류도 A, B, C로 세 가지가 있다. 원판은 원판 A, 원판 B, 원판 C와 같이 표현한다.한 번 움직이는 것은 한 막대의 가장 위에 있는 원판을 다른 막대의 가장 위로 옮기는 것이다.게임의 목표는 막대 A에는 원판 A만, 막대 B는 원판 B만, 막..

https://www.acmicpc.net/problem/15488BOJ - 나이트가 체스판을 벗어나지 않을 확률문제 유형: 다이나믹 프로그래밍, 확률론, 수학문제 난이도: Gold IV시간 제한: 2초메모리 제한: 512MB 문제크기가 N×N인 체스판 위에 나이트가 하나 있다. 나이트가 있는 곳의 좌표가 주어졌을 때, K번 이동한 후에 나이트가 체스판 위에 있을 확률을 구하는 프로그램을 작성하시오.나이트가 체스판 밖으로 이동하면, 다시 체스판 안으로 들어올 수 없다.체스판의 가장 윗 행은 1번 행, 가장 아랫 행은 N번 행이고, 가장 왼쪽 열은 1번 열, 가장 오른쪽 열은 N번 열이다. 체스판의 좌표는 (x, y)로 나타내고, x행 y열을 나타낸다.나이트의 위치가 (x, y)인 경우에, 이동할 수 있는..

BOJ - 네트워크 연결문제 유형: 분리 집합, 유니온 파인드문제 난이도: Platinum V시간 제한: 1초메모리 제한: 128MB 문제종빈이는 아주 큰 그룹의 총수다. 이 그룹은 1부터 N번까지의 번호로 구분할 수 있는 N개의 기업을 운영하고 있다. 현재 각 기업은 서로 독립적인 자체 컴퓨팅 및 통신센터를 가지고 있다.어느 날 종빈이는 계열사의 CTO인 서현이에게 서비스 개선을 위해 각 기업의 서버를 네트워크로 연결하여 단일 통신센터에서 관리 가능한 클러스터 형태로 구성할 것을 제안했다. 종빈이의 제안을 들은 서현이는 다음과 같은 병합 과정을 고안해냈다.클러스터 A를 제공하는 기존에 존재하는 센터 I를 고른다.클러스터 B를 제공하는 기업 J를 고른다. B는 A가 아닌 임의의 클러스터이며, J는 센터가..

https://www.acmicpc.net/problem/17841BOJ - UNIST는 무엇의 약자일까?문제 유형: 다이나믹 프로그래밍문제 난이도: Gold III시간 제한: 1초메모리 제한: 128MB 문제UNIST는 Ulsan National Institute of Science and Technology의 약자이다. 어느 날 원이는 약자가 UNIST가 되는 다른 단어가 있는지에 대해 궁금해졌다.단어 a의 길이를 len(a)로 표기하자. N개의 단어 W1, W2, ..., WN이 주어질 때, 단어 Wi (1 ≤ i ≤ N)로부터 앞에서 0글자 이상 len(Wi)글자 이하 택해서 만든 문자열을 Pi라 하자. 다시 말해, Pi는 Wi의 길이 len(Pi)인 접두사이다.Pi (1 ≤ i ≤ N)들을 적당..

https://www.acmicpc.net/problem/31005BOJ - 귤나무문제 유형: 애드 혹, 수학문제 난이도: Gold I시간 제한: 1초메모리 제한: 1024MB 문제서윤이네 뒷마당에는 M개의 귤이 열려 있는 커다란 귤나무가 있다.이웃집에 사는 N마리의 곰곰이들은 이 귤나무에 매일 귤을 따러 온다. 매일 1번 곰곰이부터 시작해서 N번 곰곰이까지 차례대로 귤을 따려고 시도하는데, i번 곰곰이는 A_i개의 귤을 따려고 시도하며 나무에 남은 귤이 A_i개 미만이라면 아무 행동도 하지 않는다. 10^{100} 일이 지났을 때, 귤나무에 남아있는 귤의 개수는 몇 개일지 구해보자. 입력첫째 줄에 곰곰이의 수와 귤의 개수 N, M이 공백으로 구분되어 주어진다. 1 1 둘째 줄에 각 곰곰이가 따갈 귤의..