아무 말

https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 풀이 일단 간단하게 생각할 수 있는 점화식을 정의해 보자 D[i]는 문자열 S의 i번째 까지 고려했을 때 분할의 개수의 최솟값. 자연스럽게, if(S[i]~S[j]가 팰린드롬) D[i]=D[j-1]+1 이 성립함을 알 수 있다. 이제 매번 S[i~j]가 팰린드롬임을 어떻게 확인하냐는 건데, Manacher를 이용해도 좋지만 너무 ..

https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net N이 5e6이하로 매우 크다. O(N)짜리 풀이가 필요하다. 조금 생각해보면, deque을 이용해서 범위 밖에 있는 수는 없애주면 되고, 현재 수보다 큰 수는 이제 비교할 필요가 없으므로 없애주면 된다. 아래는 코드이다. 우선순위 큐로 푼 사람도 꽤나 있을 것 같은데, 조금만 생각해서 이 풀이대로 해결하면 코딩하는데 1분도 채 안걸린다. #include using ..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 D[i]={i번째 건물을 짓는데 걸리는 총 시간} D를 위와 같이 정의 하면, 마지막으로 짓고 싶은 건물 W에서 시작하여 각 건물에 대해 건물을 짓기 위해 필요한 건물들을 짓는데에 필요한 총 시간 중 최댓값만 가져오면 됩니다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 ..

https://www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net 문자열의 최대 길이가 5000이므로 O(N^2)풀이가 가능합니다. 알파벳에서 각 문자가 등장하는 자리를 배열에 저장하고 이를 이용하여 서로 같은 부분의 길이가 얼마나 되는지를 확인하여 주면 됩니다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include using namespace ..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 심플하게 위상 정렬을 수행하는 문제 위상 정렬에 대한 설명은 아래의 포스트를 참조 https://jiuge-meogari-ps.tistory.com/14 위상 정렬(Topological Sort) 위상 정렬(topological sort)은 G가 간선 (u,v)를 가질 때 u가 v보다 순서상으로 먼저 나타나도록 모든 정점을 선형으로 나열하는 것이다. 여기..

https://www.acmicpc.net/problem/9002 9002번: Match Maker Print exactly one line for each test case . The line should contain a stable match for the test case. Each match should be represented as a sequence of the women’s id, according to the increasing order of men ’s id. The woman with the first id in the www.acmicpc.net 풀이 여자와 남자를 정점으로 하고 모든 여자와 남자를 간선으로 이으면 이는 이분 그래프를 띤다. 안정된 매칭을 만들기 위해서 아래와 같..

10403번: 나머지 https://www.acmicpc.net/problem/10430 10430번: 나머지 첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000) www.acmicpc.net 그냥 문제에서 원하는걸 출력하자. 생각을 할 필요조차 없다. 1 2 3 4 5 6 7 #include int main(){ int A,B,C; scanf("%d%d%d",&A,&B,&C); printf("%d\n%d\n%d\n%d",(A+B)%C,(A+B)%C,(A*B)%C,(A*B)%C); return 0; } Colored by Color Scripter cs 4373번: 1 https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어..

https://www.acmicpc.net/problem/9008 9008번: Castle 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 starts with integer n, the number of points, where 4 ≤ n ≤ 10,000. Each of the following www.acmicpc.net 사용 알고리즘 깊이 우선 탐색 정렬 풀이 문제의 "the interior angle formed by its two incident edge..

이 문제는 DP로 해결할 수 있다. 먼저 D[i][j][p]를 i~j까지의 가로등이 꺼져있고, p가 0일때 마징가는 i, p가 1일때 마징가는 j의 위치에 있는 상태에서 가로등 끄기를 시작했을때 낭비되는 최소한의 전력이라고 정의한다. 따라서 처음 시작위치는 M번째 가로등이므로 D[M][M][0] or D[M][M][1]의 값을 구해주면 된다. 수가 늘어나는 방향을 오른쪽, 그 반대방향을 왼쪽이라고 하면, 마징가가 현재위치에서 왼쪽, 오른쪽으로 이동하는 상황을 나누어 생각해주면 된다는 것을 쉽게 알 수 있다. 이를 생각하면 D[i][j][p]=min(D[i-1][j][0]+'이 경우 이동에 사용되는 전력', D[i][j+1][1]+'이 경우 이동에 사용되는 전력') 저 경우에 따른 이동에 사용되는 전력은 ..