넘치게 채우기

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 둘째 줄에 각 곰곰이가 따갈 귤의..

https://www.acmicpc.net/problem/2698BOJ - 인접한 비트의 개수문제 유형: 다이나믹 프로그래밍문제 난이도: Gold IV시간 제한: 1초메모리 제한: 128 MB 문제0과 1로 이루어진 수열 S가 있다. S의 첫 수는 s1이고, 마지막 수는 sn이다. S의 인접한 비트의 개수는 다음과 같이 구할 수 있다.s1*s2 + s2*s3 + s3*s4 + ... + sn-1 * sn위의 식을 이용하면 수열 S에서 인접한 1의 개수를 구할 수 있다. 예를들어, 011101101의 인접한 비트의 개수는 3이 되고, 111101101은 4, 010101010은 0이 된다.수열 S의 크기 n과 k가 주어졌을 때, 인접한 비트의 개수가 k인 수열 S의 개수를 구하는 프로그램을 작성하시오.예를..

https://www.acmicpc.net/problem/20553BOJ - 다오와 디지니의 데이트문제 유형: 그리디문제 난이도: Gold II시간 제한: 1초메모리 제한: 256MB 문제크레이지 파크의 버블힐에도 새해가 찾아왔다. 다오와 디지니는 새해가 된 기념으로 데이트를 하며 버블힐의 곳곳을 둘러보려고 한다.버블힐은 직선 형태로 연결된 $N$개의 장소로 구성되어 있다. 버블힐에는 두 장소를 잇는 길이 $N-1$개 있는데, 1 이상 $N-1$ 이하의 각 정수 $i$에 대해 $i$번 장소와 $i+1$번 장소가 길로 연결되어 있다.다오와 디지니는 데이트 계획을 분 단위로 꼼꼼하게 세우려고 한다. 다오와 디지니는 매 분마다 다음의 세 가지 행동 중 하나를 선택하여 하려고 한다. 2 을 만족하는 i번 장소에..

https://www.acmicpc.net/problem/29333BOJ - One Walk문제 유형: 그래프, 애드 혹, 해 구성하기문제 난이도: Gold II시간 제한: 1초메모리 제한: 1024MB 문제무방향 단순 그래프 G가 주어진다. 이때, 어떤 정점 S로부터 다른 정점 E까지의 보행이 단 하나가 되도록 G의 모든 간선에 방향을 부여하여라. 그래프의 보행이란 같은 정점과 간선을 여러 번 방문할 수 있는 경로를 말한다. 입력첫째 줄에 정점과 간선의 개수 N, M, 시작점과 도착점의 번호 S, E가 공백으로 구분되어 주어진다. 둘째 줄부터 M개의 줄에 간선으로 연결된 두 정점의 번호 u, v가 공백으로 구분되어 주어진다. 출력모든 간선의 방향을 어떻게 정하여도 S에서 E까지의 보행이 단 하나가 되..

https://www.acmicpc.net/problem/15569BOJ - 블록 1문제 유형: 다이나믹 프로그래밍문제 난이도: Gold III시간 제한: 1초메모리 제한: 256MB 문제여러 가지 블록들을 이용하여 직사각형 모양을 만들려고 한다. 우리에게는 1 × N 블록, 2 × N 블록, ..., N × N 블록이 무한하게 있다. 이 블록들을 사용하여 N × M 모양을 만들고 싶다. 만들 수 있는 총 방법의 수를 1999로 나눈 나머지를 구하여라. 입력첫 번째 줄에 N과 M이 입력된다. (1 ≤ N ≤ 10^2, 1 ≤ M ≤ 10^4) 출력총 가능한 경우의 수를 1999로 나눈 나머지를 출력한다. 풀이dp[i][j] = i x j의 타일을 구성하는 경우의 수로 한다. 보통의 경우는 a x n짜리(..

https://www.acmicpc.net/problem/25306BOJ - 연속 XOR문제 유형: 수학, 비트마스킹문제 난이도: Gold IV시간 제한: 1초메모리 제한: 1024MB 문제준원이는 다음과 같이 A에서 B까지의 자연수들을 나열했다. A, A+1, A+2, \dots, B-2, B-1, B이 수들에 모두 비트 XOR을 취한 값을 구하라. 입력두 자연수 A, B가 공백을 사이에 두고 주어진다. 출력A 이상 B 이하인 모든 자연수들을 XOR한 값을 구하여라. 풀이물론 일일이 구하면 TLE에 걸린다.대신, f(x)를 1 ... x까지의 XOR sum이라고 해보자. 최종적으로 f(b) ^ f(a-1)을 구하면 되는 것이다. f(x), 즉 1 ... x의 XOR sum은 다음처럼 간단한 규칙을 가진..