정리충의 정리노트

0. 문제 주소 https://www.acmicpc.net/problem/3948 3948번: 홍준이의 친위대 문제 홍준 왕국의 국왕 홍준이는 자신을 호위하는 N명의 친위대 병사가 있다. 병사들의 키는 모두 다르다. 홍준이는 그들을 일렬로 세울 때, 키 순서대로 세우는 것보다 맨 끝 두 병사를 제외한 � www.acmicpc.net 1. 풀이 처음엔 1차원 dp 배열로 점화식을 세워보려고 했으나 실패했다. 탑다운으로 현재 위치에 서려는 사람 기준 남아있는 사람들 중에 이 사람보다 키가 작은 사람 / 큰 사람의 수와 함께 다음에는 이 사람보다 큰 사람이 와야 하는지 여부를 파라미터로 사용한다. 2. 풀이 코드 * 유의할 점 #include #define ll long long using namespace ..

0. 문제 주소 https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 사건이 발생된 위치가 한 줄에 하나씩 주어진다. 경찰차들은 이 사건들을 주어진 순서대로 처리해야 한다. 각 위치는 동서방향 도로 번호를 나타내는 정수와 남북방향 도로 번호를 나타내는 정수로 주어지며 두 정수 사이에는 빈칸이 하나 있다. 두 사건이 www.acmicpc.net 1. 풀이 메모이제이션 없이 풀려면 2^1000가지 경우를 다 봐야 한다. 사건이 W개 있을 때, 0번째 사건이 (1, 1)..

0. 문제 주소 https://www.acmicpc.net/problem/10714 10714번: 케이크 자르기 2 문제 JOI 군과 IOI 양은 쌍둥이 남매이다. JOI 군은 최근 과자 만들기에 푹 빠졌기 때문에, JOI 군은 오늘도 케이크를 만들어서 먹으려고 했지만, 막 구워진 참에 냄새를 맡고 온 IOI 양이 왔기 때문에 두 명이 케이크를 나누어 먹기로 했다. 케이크는 둥그런 모양을 하고 있다. 어느 점에서부터 직선으로 칼집을 넣어 케이크를 N 개의 조각으로 나눈 뒤, 각 조각마다 1부터 N 까지 반시계방향으로 번호를 매긴다. 즉, 1 ≦ i ≦ N에 대해, i www.acmicpc.net 1. 풀이 사선 dp 문제들과 유사하게, 구간을 고려하는 점은 비슷하지만, dp 테이블의 정의를 다르게 해야 ..

0. 문제 주소 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다. www.acmicpc.net 1. 풀이 약간 내리막길 문제랑 비슷한 느낌이 들었다. 맨 처음엔 칸 별로 연결관계를 만들어 BFS를 돌리려고 했으나... 멍청한 생각이었다. DFS + DP의 풀이를 사용한다. top-down은 어렵다 ㅠ 주의해야 할 점은 cycle의 유무이다. [PS/BFS & DFS] - [BOJ] 9466: 텀 프로젝트에서 DFS를 ..

0. 문제 주소 https://www.acmicpc.net/problem/2624 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다. 20 = 10×2 20 = 10×1 + 5×2 20 = 10×1 + 5×1 www.acmicpc.net 1. 풀이 [PS/DP] - [BOJ] 9084: 동전 참고 개수의 제한에 주의할 필요가 있다. [PS/DP] - [BO..

0. 문제 주소 https://www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 풀이 소문자를 대문자로 써놔서 근데 또 돌아가서 시간만 날린 문제...지만 좋은 문제 가장 먼저 필요한 건 i 개의 a와 j 개의 z로 만들 수 있는 단어의 개수를 저장할 2차원 dp 테이블이다. 단순하게 (i+j) ! / ( i ! ) ( j ! ) 으로 계산할 수 있지만 당연히 오버플로우가 나기 때문에, dp를 이용한다. K의 값이 10억 이하이므로, 그 이상은 오버플로우 처리를 위해 값이 10억을 초과하면 10억 + ..

0. 문제 주소 https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자. www.acmicpc.net 1. 풀이 교점이 생기면 안 된단다. 그냥 LIS 문제다. LIS 풀이는 여러가지가 있지만, 이 문제에선 N 제한이 40000이므로 dp, 즉 O(N^2)로는 풀 수 없다. lower_bound를 사용하면 O(n log n)으로 쉽게 풀 수 있다. 먼저 빈 배열 d를 설정해두고, 기존 배열..

0. 문제 주소 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데, 이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다. 예를 들어, 철수와 영희, 철수와 만수, 영희와 순희가 서로 친구 관계라면 이를 표현하 www.acmicpc.net 1. 풀이 대표적인 tree DP 문제. 먼저 연결 관계로 vector 배열 child를 이용해 트리를 만들고..

0. 문제 주소 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 www.acmicpc.net 1. 풀이 [PS/DP] - [BOJ] 11049: 행렬 곱셈 순서와 똑같은 기법을 사용하는 dp 문제. 마찬가지..

0. 문제 주소 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다. www.acmicpc.net 1. 풀이 2차원 배열을 이용하여 모든 구간별 정보를 메모이제이션 하는 dp 문제. 다시 말해서, i번째 행렬부터 j번째 행렬까지 곱했을 때의 최소 곱셈 횟수를 저장할 것이기 때문에, 이 정보들을 이용하기 위해선 곱셈 형태를 큰 부분 두 개로 나누어야 한다. A, B, C, D 4개의 행렬이 있다고 가정해 보자. 메모이제이션을 통해 A ~ C , 그리고 B ~ D ..