이동식 저장소

매운 거 먹기 좋은 날씨인데.. 나는 뭐 하냐.. 15824번: 너 봄에는 캡사이신이 맛있단다 한 줄에 모든 조합의 주헌고통지수 합을 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 뭔가 어려워 보이는 문제이다. 음식의 모든 조합을 먹어 보라고 했으니 $2^{N}$개의 조합을 모두 따져 볼까? $O(2^{N})$ 풀이 음식점의 모든 조합을 구하고, 모든 조합의 주헌고통지수를 더한다. 1초만에 떠올릴 수 있는 풀이지만, 당연히 맞을 리가 없다. Small 태스크만 봐도 $N=3000$이다. 아무래도 조금 더 생각해봐야 할 것 같다. $O(N^{2})$ 풀이 위에서 말했듯이, 이 음식점의 모든 음식 조합은 $2^{N}$개이다. 상식적으로 $2^{N}$개를 일일이 다 따져볼 수..

2560번: 짚신벌레 첫째 줄에 a, b, d, N을 나타내는 네 정수가 빈칸 하나를 사이에 두고 차례로 주어진다. 단, 0＜a＜b＜d≤10,000이고, 1≤N≤1,000,000이다. www.acmicpc.net 규칙에 따라 변하는 짚신벌레의 상태를 추적하는 문제이다. 딱 봐도 dp스럽지 않은가? 짚신벌레의 상태는 날짜에 의해서만 변하므로, $i$번째 날의 값을 알면 $i+1$번째 날의 값도 알 수 있다. 다음을 정의한다. $t[i][j]$: $i$번째 날에 상태가 $j$로 바뀌는 짚신벌레의 수 $sum[i][j]$: $i$번째 날에 상태가 $j$인 짚신벌레의 수 ($t$의 부분합이라고 생각하면 좋다) 상태 $j$는 다음과 같다. $j = 0$: 태어남 (태어났지만 성체는 아님) $j = 1$: 성체가 ..

16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net C언어에서 문자열 처리를 배울 때 흔히 연습하는 사칙연산 문제이다. 문제에서 연산자의 우선순위는 모두 동일하다고 하였으므로 기본적으로 왼쪽에서부터 하나씩 계산해야 한다. 괄호 추가 이제 괄호를 추가해 보자. 괄호 안에는 하나의 연산자만 들어가야 하며, 괄호를 중첩해서 사용할 수는 없다. 직관적으로는 매우 이해하기 쉬운 조건이지만, 의외로 구현하기에는 까다로울 수 있다. 엄밀하게 과정을 정의하면 다음과 같다. 연산자의 양 옆 피연산자를 괄호로 묶어야 한..

20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 문제 이해 문제 설명에서 헷갈리기 쉬운 부분을 정리한다. 평면 상에 점 $n$개가 주어지는데, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 평면 위의 점이 주어진다고 한다. 그런데 점의 좌표가 없다. 이게 뭐지? 하고 당황할 수 있지만 두 번째 조건이 중요하다. 어느 세 점도 일직선 위에 놓이지 않는다고 한다. 좌표가 주어지지 않았지만 대략 이런 형태의 모양을 상상할 수 있다. 바로 정$n$각형이다. 정$n$각형의 꼭짓점은 위의 조건을 정확히 만족한다...

오랜만에 문제 풀이를 작성해 본다. 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net 친구를 돈으로 사려는 불쌍한 준석이의 이야기이다. 음.. 나름 꿀알바 같기도 하고? 친구의 친구는 친구다라는 말이 매우 중요하다. 준석이가 학생 $i$와 친구가 되었다고 해 보자. 친구의 친구는 친구이므로 준석이는 학생 $i$번의 친구와도 친구이다. 같은 원리로 학생 $i$번의 친구의 친구와도 친구이다. 따라서 서로 친구인 그룹의 구성원 중 한 명에게만 돈을 주면 그 그룹의 모든 사..