넘치게 채우기

https://www.acmicpc.net/problem/1660BOJ - 캡틴 이다솜문제 유형: 다이나믹 프로그래밍문제 난이도: Gold V시간 제한: 2초메모리 제한: 128MB 문제캡틴 이다솜은 자신의 해적선에 적을 공격하기 위한 대포알을 많이 보관해 놓는다. 다솜이는 미적감각이 뛰어나기 때문에, 대포알은 반드시 사면체 모양으로 쌓아놓아야 한다고 생각한다. 사면체를 만드는 방법은 길이가 N인 정삼각형 모양을 만든다. 그 위에 길이가 N-1인 정삼각형 모양을 얹고 그위에 계속 해서 얹어서 1크기의 정삼각형 모양을 얹으면 된다.예를 들어, 사이즈가 3크기의 한 더미 모양은 다음과 같다. X X X X X X XX X X각각의 삼각형은 1, 3, 6, 10 ,..... 와 같이 대포알을 가지고 있다..

https://www.acmicpc.net/problem/18116BOJ - 로봇 조립문제 유형: 유니온-파인드, 분리 집합문제 난이도 : Gold IV시간 제한: 4초메모리 제한: 1024MB 문제성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의 부품인지 알 수 있다. 그래서 성규는 호재의 지시에 따라 부품들을 정리하기로 하였다.부품들은 1부터 106까지의 정수로 표현된다. 그리고 부품 i가 속한 로봇은 robot(i)라고도 표현한다. 예를 들어, 부품 11과 부품 22가 로봇 A의 부품이라고 알고 있는 경우, robot(11)은 로봇 A를 의미하고, robot(22..

https://www.acmicpc.net/problem/21319BOJ - 챔피언(Easy)문제 유형: 그리디, 이분 탐색, 시뮬레이션문제 난이도: Gold I시간 제한: 2초메모리 제한: 1024MB 문제입력 조건 외 챔피언 (Hard)와의 차이는 없다.민겸이는 세계적인 격투기 선수 육성 회사의 회장이다. 민겸이는 격투기 선수의 영입을 위해 세계 격투기 챔피언십을 관람하기로 했다. 세계 격투기 챔피언십의 규칙은 아래와 같다.격투기 선수는 N명이고, 일렬로 서 있다. 선수들은 각각 전투력을 가지고 있다. 격투기 선수들은 양쪽으로 이웃한 두 명의 선수들 중 한 명에게 싸움을 걸어 격투를 벌인다. 이 때, 전투력이 높은 격투기 선수가 승리한다. 격투에서 승리한 선수는 자신감이 붙어 전투력이 1 증가한다. ..

https://www.acmicpc.net/problem/33516BOJ - skeep 문자열문제 유형: 문자열 처리, 스택문제 난이도: Gold III시간 제한: 1초메모리 제한: 1024MB 문제skeep은 자신의 오프라인 팬클럽을 운영 중이다. 어느덧 인기스타가 된 skeep의 팬클럽에는 사람들이 몰려 공간이 부족해졌다.이에 skeep은 자신의 진정한 팬만 팬클럽에 입장시키기로 결심했다.skeep의 진정한 팬이라면 skeep이라는 문자열을 좋아할 것이라 믿으며, 이를 판별하기 위해 다음과 같은 문제를 준비했다.길이가 N$N$인 알파벳 소문자로 구성된 문자열이 주어진다. 이 문자열에서 다음 작업을 원하는 만큼 수행할 수 있다.문자열에서 skeep이라는 연속한 부분 문자열을 찾아 s를 제외한 소문자 알..

https://www.acmicpc.net/problem/2224BOJ - 명제 증명문제 유형: 플로이드-워셜, 문자열 처리문제 난이도: Gold IV시간 제한: 2초메모리 제한: 128MB 문제수학, 혹은 논리학에서 만약 무엇 이라면 뭣 일 것이다 하는 식의 명제가 널리 쓰인다. 예를 들어 "P이면 Q일 것이다." 라는 명제는 “P => Q” 라는 기호로 표현된다. 이때의 P를 전건, Q를 후건이라고 한다.논리학에서 어떤 명제를 증명할 때 가장 널리 쓰이는 방법 중 한 가지가 바로 삼단 논법이다. 만약 두 명제 “P => Q", "Q => R" 가 모두 참이면, 명제 "P => R"이 역시 참이 된다. 이러한 방법을 사용했을 때 명제 ”P => R"이 증명되었다고 한다.어떤 참인 명제가 주어졌을 때, ..

https://www.acmicpc.net/problem/17619 BOJ - 개구리 점프문제 유형: 분리 집합, 유니온 파인드, 정렬문제 난이도: Gold III시간 제한: 1초메모리 제한: 512MB 문제통나무 N개가 가로 (수평) 방향으로 연못에 떠 있다. 개구리는 한 통나무 A에서 다른 통나무 B로 정확히 수직 방향으로 점프할 수 있다. 단, 점프할 때 다른 통나무 위를 (끝 점 포함) 지나면 안된다.예를 들어 에서 1번 통나무에서 2번 통나무로 점선을 따라 개구리가 점프하는 것이 가능하다. 1번 통나무에서 2번 통나무로 점프한 후 다시 3번 통나무로 점프하면 1번 통나무에서 3번 통나무로 이동하는 것이 가능하다. (통나무 위에서 걸어서 움직이는 것은 언제든 가능하다.) 통나무들의 위치를 입력받아..

https://www.acmicpc.net/problem/20168BOJ - 골목 대장 호석 - 기능성문제 유형: 그래프, 최단경로, 브루트 포스문제 난이도: Gold V시간 제한: 3초메모리 제한: 512MB 문제소싯적 호석이는 골목 대장의 삶을 살았다. 호석이가 살던 마을은 N 개의 교차로와 M 개의 골목이 있었다. 교차로의 번호는 1번부터 N 번까지로 표현한다. 골목은 서로 다른 두 교차로를 양방향으로 이어주며 임의의 두 교차로를 잇는 골목은 최대 한 개만 존재한다. 분신술을 쓰는 호석이는 모든 골목에 자신의 분신을 두었고, 골목마다 통과하는 사람에게 수금할 것이다. 수금하는 요금은 골목마다 다를 수 있다.당신은 A 번 교차로에서 B 번 교차로까지 C 원을 가지고 가려고 한다. 호석이의 횡포를 보며..

https://www.acmicpc.net/problem/17089BOJ - 세 친구문제 유형: 브루트 포스, 그래프, 정렬문제 난이도: Gold V시간 제한: 2초메모리 제한: 512MB 문제N명의 사람이 있고, 여기서 세 사람 A, B, C를 고르려고 한다. 세 사람은 모두 친구여야 한다.세 사람을 고르는 방법은 매우 많이 있을 수 있다. 이때, A의 친구 수 + B의 친구 수 + C의 친구 수가 최소가 되어야 한다. 친구 수의 합을 계산할 때, 세 사람은 빼고 계산해야 한다. 즉, A의 친구 수를 계산할 때, B와 C는 빼고 계산해야 하고, B의 친구 수를 계산할 때는 A와 C, C의 친구 수를 계산할 때는 A와 B를 빼고 계산해야 한다. 입력첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친..

https://www.acmicpc.net/problem/20327BOJ - 배열 돌리기 6문제 유형: 구현, 시뮬레이션문제 난이도: Gold II시간 제한: 1초메모리 제한: 512MB 문제크기가 2N×2N인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 8가지가 있고, 연산에는 단계 ℓ (0 ≤ ℓ  1번 연산은 각 부분 배열을 상하 반전시키는 연산이다.2번 연산은 각 부분 배열을 좌우 반전시키는 연산이다.3번 연산은 각 부분 배열을 오른쪽으로 90도 회전시키는 연산이다.4번 연산은 각 부분 배열을 왼쪽으로 90도 회전시키는 연산이다.5, 6, 7, 8번 연산은 부분 배열을 한 칸으로 생각하고 적용시킨다. 즉, 부분 배열의 안에 있는 값은 변하지 않는다.5번 연산은 배열을 상하 반전시..

https://www.acmicpc.net/problem/1241BOJ - 머리 톡톡문제 유형: 수학, 정수론문제 난이도: Gold V시간 제한: 2초메모리 제한: 128MB 문제엄지 생일 기념으로 학생들은 파티를 하고 있다. 엄지는 N(1≤N≤100,000)명의 학생에게 1부터 N번까지 차례대로 번호를 부여하였고 그들을 순서대로 빙 둘러앉아 원을 만들게 하였다. (즉 i번째 학생은 i-1과 i+1학생 사이에 앉아있다. 단, N번째 학생은 N-1번째 학생과 첫 번째 학생 사이에 앉아있다.)N명의 학생은 둘러앉아 "머리톡톡" 게임을 하려한다. 게임 규칙은 다음과 같다. 각각의 학생은 자신의 머리 위에 1,000,000 이하의 자연수 중 하나를 쓴다. 그리고 1번부터 N번 학생까지 한 명씩 차례대로 일어나 ..