MathTrauma

문제 링크 : https://www.acmicpc.net/problem/2477 2477번: 참외밭 첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지 www.acmicpc.net 이 문제 자체 보다 생각해 봐야할 것이 있어서 기록해 둔다. 1. 방향에 대한 정보는 필요없다?! 주어진 문제이 도형은 큰 직사각형에서 작은 직사각형을 제거한 형태이다. 둘레의 길이라는 측면에서 보면 큰 직사각형을 형성하는 두 변의 길이의 합이 전체의 절반이 된다. 이 사실을 이용하면 방향에 대한 정보는 필요가 없다. 이렇게 해결하는 코드는 다음과 같다. #include using..

문제 링크 : https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 선행 관계가 작업 번호 순으로 주어지니 딱히 전처리할 것들은 없다. dp[i] 는 i 번째 작업을 마칠 수 있는 최소 시간으로 정의한다. $a[i]$ 를 i 번 작업에 소요되는 시간, $S_i$ 를 i 번 작업에 필요한 선행 작업이라 할 때, 다음 관계식이 성립한다. $$ dp[i]= \max\limits_{j \in S_i } dp[j] + a[i] $$ #include ..

문제 링크 : https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 트라이(trie) 기본 문제. 아호-코라식(Aho-Corasick) 알고리즘을 복습하기 전에 다시 풀어 봤다. 입력받은 문자열을 저장할 strs를 동적으로 할당하면 메모리는 많이 절약되지만 시간은 살짝 더 걸린다. #include using namespace std; vector strs; struct trie { char c; bool isEnd; trie*..

문제 링크 : https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 동전의 종류 N 이고 만들어야 할 금액은 V 이다. $recur(n,v)$ 는 $n \; (1\le n \le N)$ 번 이하의 동전들을 사용해서 v 금액을 만드는 방법의 수이다. #include using namespace std; int N,V; int arr[21]; int dp[21][10001]; int recur(int n, int v){ if(n==1){..

문제 링크 : https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 어설픈 영어 실력에도 불구하고 원문이 이해하기 쉬워서 그쪽으로 내용을 정리한다. n 개의 점의 좌표가 주어지고 그 점들 중 일부는 m 개의 도로로 연결되어 있다. 아직 연결되지 않은 점들을 최소의 비용(도로의 길이)으로 연결하는 문제이다. 1. 미리 주어진 m 개의 간선(도로)를 제한 나머지 모든 점들 사이에 간선을 만들고 비용 오름차순으로 정렬한다. 2...

문제 링크 : https://www.acmicpc.net/problem/11503 11503번: Tree Edit Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case consists of two lines. The first line contains a string representing T1 and the second line www.acmicpc.net 문제가 길어서 대충 읽었다가 'ordered tree' 라는 조건을 놓쳐서 시간을 많이 허비했다. 자식들의 순서..

문제 링크 : https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 가장 마지막에 오는 것은 내림차순이라는 문제의 설명이 모든 것을 말해 주고 있다. N=5 인 경우 즉, 1 2 3 4 5 로 이루어지는 한 순열을 관찰해 보자. $$ 2 \; 3 \; 5 \; 4 \; 1 $$ 1. 순열에서 가장 긴 내림차순으로 이루어진 마지막 부분(suffix)을 찾았을 때, 앞 부분이 2 3 으로 시작되는 순열의 마지막임을 알게 된다. 그렇다면 앞 부분 2 3 을 바꾸어야 할 것이다. 2. 뒤의 5 4 1 중에서 3 보다..

문제 링크 : https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net $ dp[n][k] $ 는 n 을 만드는 과정에서 마지막 수가 k( =1,2,3)인 경우의 수를 뜻한다. 1. Bottom-Up 예를 들어 보자. dp[10][2] 는 2로 끝나면서 10 을 만드는 경우의 수이다. 2 를 연이어 쓸 수 없으니 덧붙일 수 있는 것은 1, 3. 1 을 덧붙여 dp[11][1] 을 만드는데 기여하고, 3을 덧붙여서 dp[13][3] 을 만드는데 기여한다. $ dp[i][j] $ 를 i 를 1 부터 차례로 ..