넘치게 채우기

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..

https://www.acmicpc.net/problem/21772BOJ - 가희의 고구마 먹방문제 유형: 백트래킹, 브루트포스, 구현문제 난이도: Gold V시간 제한: 2초메모리 제한: 512MB 문제가희는 고구마를 정말 좋아합니다. 이번에도 어김 없이 고구마 냄새가 났는데, 고구마가 보이지 않습니다. 오빠가 방 안에 고구마를 숨겨 놓았기 때문입니다.오빠는 가희에게 하나의 게임을 제안하고, 게임의 규칙을 설명해 주었습니다. 게임 규칙은 아래와 같습니다.가희는 1초마다 상하좌우 방향 중 한 방향으로 1번 이동하거나, 이동하지 않고 그 자리에 머무를 수 있습니다.가희가 이동한 지점에 고구마가 있는 경우에는, 고구마를 먹습니다. 고구마를 먹는 데 걸리는 시간은 없다고 가정합니다.가희가 고구마를 먹으면, 고..

https://www.acmicpc.net/problem/2066BOJ - 카드놀이문제 유형: 다이나믹 프로그래밍문제 난이도: Gold I시간 제한: 2초메모리 제한: 128MB 문제한 벌의 트럼프 카드 중 36장의 카드를 이용하여 하는 놀이가 있다. 각각의 카드들은 4장씩, 9개의 그룹으로 나눠서 놓이게 된다. 카드를 놓을 때에는 앞면(무늬와 숫자가 적혀 있는 면)이 보이도록 놓게 된다. 각각의 카드는 두 개의 문자로 나타낼 수 있는데, 하나는 숫자(6~9, T, J, Q, K, A)와 무늬를 나타내는 문자(S, D, H, C)로 이루어진다.이 놀이의 목적은 이 카드들 중에서 두 장의 카드를 들어내는 과정을 18번 반복하여 모든 카드를 들어내는 것이다. 카드를 들어낼 때에는 서로 다른 그룹에 있는 카드..

https://www.acmicpc.net/problem/17472BOJ - 다리 만들기 2문제 유형: bfs/dfs, 그래프, MST, 최단경로, 구현문제 난이도: Gold I시간 제한: 1초메모리 제한: 1024MB 문제섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를..

https://www.acmicpc.net/problem/26009BOJ - 험난한 등굣길문제 유형: bfs, 그래프문제 난이도: Gold II시간 제한: 2초메모리 제한: 1024MB 문제통학러 재헌이는 1교시 수업을 듣기 위해 아침 일찍 학교에 가려고 한다. 재헌이가 사는 지역은 크기가 N×M 인 격자로 나타낼 수 있는데, i행 j열에 해당하는 칸을 (i,j)로 나타낼 때 재헌이는 현재 (1,1)에, 학교는 (N,M)에 위치해 있다. 재헌이는 상하좌우로 한 칸씩 이동할 수 있고 지역 바깥으로 나갈 수는 없다.등굣길은 순탄치만은 않은데, 이 지역에는 K개의 정체 구역이 있다. i$i$번째 정체 구역은 세 정수 Ri,Ci,Di로 표현되며, 이는 (Ri,Ci)로부터 거리가 Di 이하인 칸들에는 극심한 교통..

https://www.acmicpc.net/problem/2831BOJ - PLES문제 유형: 정렬, 투포인터문제 난이도: Gold IV시간 제한: 1초메모리 제한: 128MB 문제남자 N명과 여자 N명이 상근이가 주최한 댄스 파티에 왔다. 상근이는 모든 사람의 키를 알고있다. 각 남자는 모두 여자와 춤을 출 수 있고, 여자는 남자와 춤을 출 수 있다. 모든 사람은 많아야 한 사람과 춤을 출 수 있다.모든 남자는 자신이 선호하는 여자와 춤을 추려고 한다. 각 남자가 선호하는 여자는 두 가지 유형이 있는데, 한 유형은 자신보다 키가 큰 여자이고, 다른 유형은 자신보다 키가 작은 유형이다. 여자도 남자와 마찬가지로 자신이 선호하는 남자와 춤을 추려고 한다. 각 여자가 선호하는 남자도 남자와 비슷하게 두 유형..

https://www.acmicpc.net/problem/14428BOJ - 수열과 쿼리 16문제 유형: 세그먼트 트리문제 난이도: Gold I시간 제한: 2초메모리 제한: 512MB 문제길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109)2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 인덱스를 출력한다. 그러한 값이 여러개인 경우에는 인덱스가 작은 것을 출력한다. (1 ≤ i ≤ j ≤ N, 1 ≤ v ≤ 109)수열의 인덱스는 1부터 시작한다. 입력첫째 줄에 수열의 크기 N이 주어진다. (1 ≤ N ≤ 100,000)둘째 줄에는 A1, A2,..

https://www.acmicpc.net/problem/5625BOJ - 페스트리문제 유형: 누적 합, 스위핑문제 난이도: Gold III시간 제한: 1초메모리 제한: 128MB 문제상근 바게트에서 삼각 페스트리 N개를 구웠다. 모든 페스트리는 2차원 평면 위에서 정수 좌표 꼭짓점을 가지는 삼각형으로 나타낼 수 있다.상근이의 말썽꾸러기 아들 정인이는 커다란 칼을 들고 페스트리를 자르려고 한다. 정인이는 좌표평면에서 수직 방향(x = c)이나 수평 방향(y = c)으로 칼질을 한다. 정인이가 칼질을 할 때, 총 몇 개의 페스트리가 잘리는지 구하려고 한다. 페스트리가 칼질로 두 부분으로 나누어졌을 때, 두 부분의 넓이가 0보다 크면 잘린 것이다.페스트리의 위치와 정인이의 칼질이 주어졌을 때, 몇 개의 페스..