넘치게 채우기

https://www.acmicpc.net/problem/3865BOJ - 학회원문제 유형: 문자열 처리, bfs, 그래프, 파싱문제 난이도: Gold IV시간 제한: 1초메모리 제한: 128MB문제상근이는 Sogang ACM-ICPC Team의 회장이다. 서강대학교 컴퓨터 학생들은 하나 또는 그 이상의 학회에 소속되어 있다. 상근이는 학생들이 어떤 학회에 소속되어 있는지 조사해보려고 한다.상근이는 학회원의 정보를 다음과 같이 작성한다. 아래 예시는 sisobus와 weissblume은 icpc의 학회원이라는 뜻이다.icpc:weissblume,sisobus.콜론(:)의 앞에는 학회의 이름이 쓰여 있고, 뒤에는 학회원이 주어진다.어떤 학회는 모든 회원이 다른 학회에 소속되어 있을 수도 잇다. 따라서, 학..

https://www.acmicpc.net/problem/28435BOJ - 배수 피하기문제 유형: 수학, 조합론문제 난이도: Gold II시간 제한: 1초메모리 제한: 1024MB 문제크기 N인 집합 A={A1,A2,⋯,AN}와 정수 K가 주어집니다. A의 부분집합 S가 좋은 집합이라는 것은 다음 조건을 모두 만족시킴을 의미합니다. S에는 두 개 이상의 수가 포함되어 있습니다. S의 서로 다른 두 원소 a,b∈S에 대해서, a+b는 K의 배수가 아닙니다.좋은 집합의 개수를 출력하세요. 입력첫 줄에 정수의 개수 N과 문제의 정수 K가 공백으로 구분되어 주어집니다. (2≤N,K≤100000)둘째 줄에 N개의 서로 다른 정수 A1,A2,⋯,AN이 공백으로 구분되어 주어집니다. (1≤Ai≤10^9) 출력첫 줄..

https://www.acmicpc.net/problem/23880BOJ - Walking Home문제 유형: 다이나믹 프로그래밍문제 난이도: Gold IV시간 제한: 2초메모리 제한: 1024MB 문제Bessie the cow is trying to walk from her favorite pasture back to her barn.The pasture and farm are on an N×N grid (2≤N≤50), with her pasture in the top-left corner and the barn in the bottom-right corner. Bessie wants to get home as soon as possible, so she will only walk down and t..

https://www.acmicpc.net/problem/2262BOJ - 토너먼트 만들기문제 유형: 그리디문제 난이도: Gold IV시간 제한: 2초메모리 제한: 128MB 문제월드시에서는 매년 n명의 사람들이 모여 월드 크래프트라는 게임의 토너먼트 대회를 치른다. 이 게임은 특성상 실력만이 승패를 좌우하기 때문에, 아무리 실력이 엇비슷한 사람이 시합을 치러도 랭킹이 높은 사람이 반드시 이기게 된다. 따라서 월드시에서는 게임을 흥미진진하게 만들기 위해서, 부전승을 여러 번 만들더라도 각 시합에 임하는 선수들의 랭킹 차이를 비슷하게 만들려고 한다.토너먼트를 만들 때에는 이미 추첨이 된 순서대로 선수들을 배치하고, 왼쪽에서 오른쪽의 순서가 어긋나지 않도록 시합을 정한다. 물론 부전승을 임의로 만들 수 있지..

https://www.acmicpc.net/problem/1838BOJ - 버블 정렬문제 유형: 정렬문제 난이도: Gold I시간 제한: 1초메모리 제한: 128MB 문제버블 정렬이란 배열에서 서로 인접해 있는 값을 비교해서 작은 값이 더 뒤에 있을 때 두 값을 바꾸어 주는 과정을 계속 반복하는 정렬 방법이다. N개의 서로 다른 정수가 A[0], A[1], ..., A[N-1]의 정수형 배열에 저장되어 있고, 이를 오름차순으로 정렬하기 위해 태국이는 다음과 같은 코드를 작성하였다.for (i=0; i A[j+1]) { flag = 1; temp = A[j]; A[j] = A[j+1]; A[j+1] = temp; }..

https://www.acmicpc.net/problem/11727BOJ - 2xn 타일링 2문제 유형: 다이나믹 프로그래밍문제 난이도: Silver III시간 제한: 1초메모리 제한: 256MB 문제2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 풀이점화식은 다음과 같다:dp[i] = (dp[i-2] * 2 + dp[i-1]) % MOD 2칸 전으로부터 1 x 2를 두 개 쌓은것을 이어붙이거나, 2x2하나를 이어붙이기, 또는 1칸 전으로부터 2 ..

https://www.acmicpc.net/problem/14169BOJ - Lasers and Mirrors문제 유형: 다익스트라, 0-1 BFS, 최단 경로, 그래프, 좌표 압축문제 난이도: Platinum V시간 제한: 2초메모리 제한: 512MB 문제For some reason, Farmer John's cows always seem to be running laser light shows.For their latest show, the cows have procured a large powerful laser -- so large, in fact, that they cannot seem to move it easily from the location where it was delivered. T..

https://www.acmicpc.net/problem/13976BOJ - 타일 채우기 2문제 유형: 다이나믹 프로그래밍, 분할 정복, 수학문제 난이도: Platinum V시간 제한: 2초메모리 제한: 512MB 문제3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력첫째 줄에 N(1 ≤ N ≤ 1,000,000,000,000,000,000)이 주어진다. 출력첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. 풀이3 x n을 1 x 2또는 2 x 1 타일로 채우는 경우의 수의 점화식은T(n) = 4 * T(n-2) - T(n-4)이다. T(n-4)를 유도하기 위해서, T(n-6)까지가 필요하다 (n >= 8부터) T(n), T(n-2), T(n-4..

https://www.acmicpc.net/problem/23889BOJ - 돌 굴러가유문제 유형: 구간합, 그리디, 정렬문제 난이도: Gold IV시간 제한: 1초메모리 제한: 512MB 문제경기북과학고등학교에 숨겨져 있는 알프스 산맥에는 많은 마을이 있다. 알프스 산맥에 살던 도현이는 충격적인 사실을 듣게 되었다. 바로, 내일 큰 돌들이 굴러가 마을을 덮칠 것이라는 사실이었다.집은 부서지지 않겠지만, 마을의 아이들이 쌓아놓은 모래성이 부서질 것이므로 매우 심각한 일이었다. 돌은 모두 왼쪽에서 오른쪽으로 계속 굴러가며, 돌은 굴러가기 시작하는 마을의 모래성부터 부수기 시작한다.다행히도 도현이에게는 굴러오는 돌을 막을 수 있는 벽이 있다. 하지만, 돌의 개수가 도현이가 가지고 있는 벽의 개수 이상인 것이..

https://www.acmicpc.net/problem/16305BOJ - Birthday Boy문제 유형: 문자열 처리, 애드혹, 파싱, 정렬문제 난이도: Gold V시간 제한: 1초메모리 제한: 512MB 문제Bobby has just joined a new company, and human resources has asked him to note his birthday on the office calendar. Bobby the Birthday Boy wants to feel special! Also, Bobby the Birthday Boy does not mind lying for attention.He notices that the longer people have not celebrated..