Hanbit the Developer

정의CHT는 특정 조건의 DP 점화식에 활용할 수 있는 최적화 기법입니다. [조건]1. dp[i] = min(a[j] * b[i] + dp[j]) (0 2. 수열 a가 단조감소 한다. dp[N]은 이중 포문을 돌아야 구할 수 있으므로 시간 복잡도는 O(N^2)입니다. 하지만 CHT를 활용하면 O(NlogN)으로 최적화를 할 수 있게 됩니다. 접근 방식CHT에서는 dp[i]를 구할 때 '일차 함수'를 활용합니다. 아래 표에서 파란색 식을 보면 a[0] * b[i] + dp[0]의 꼴을 하고 있습니다. 여기서 b[i]를 x로 치환을 하면 a[0] * x + dp[0] 형태가 됩니다. 즉 j = 0일 때의 함수 f0는 a[0] * x + dp[0]입니다. j = 1일 때의 함수 f1은 a[1] * x + dp..

https://www.acmicpc.net/problem/18186 18186번: 라면 사기 (Large) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i www.acmicpc.net 아이디어 1. 블럭 하나를 여러 블럭으로 나누어 돈을 절약할 수 있다. B, C 값에 따라서 1, 2, 3번 구매 옵션의 비용이 달라진다. 경우에 따라 (블럭 3 비용) > (블럭 1 비용) + (블럭 2 비용)이 성립하는 등의 케이스가 발생할 수 있다. 극단적으로, B = 1, C = 100인 경우 블럭 1은 1원, 블럭 2는 101원이 들기 때문에 블럭 1로 나누어 구매하는 ..

https://www.acmicpc.net/problem/2866 2866번: 문자열 잘라내기 첫 번째 줄에는 테이블의 행의 개수와 열의 개수인 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 이후 R줄에 걸쳐서 C개의 알파벳 소문자가 주어진다. 가장 처음에 주어지는 테이블에는 열을 읽어서 문자 www.acmicpc.net - (첫번째 해결 방법) 접근 문자열을 거꾸로 생각하고 여기에 Trie를 접목하였다. import sys input = sys.stdin.readline class Node: __slots__ = ['childs'] def __init__(self): self.childs = {} class Trie: __slots__ = ['root'] def __init__(self): se..

https://www.acmicpc.net/problem/15653 15653번: 구슬 탈출 4 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net > 접근 보드를 변경시켜 가면서 DP의 값을 참조하면서 탐색을 해야하는 것은 명백한데, 문제는 어떻게 DP를 이용하느냐였다. 우선 보드는 빨간 구슬과 파란 구슬만이 움직이게 되므로 이 두 개의 좌표를 통해 DP에 접근할 수 있으면 된다. 좌표계는 10x10가 최대 범위이므로 (x, y)라는 두 개의 요소로 구성된 좌표를 하나의 정수로 치환하는 트릭..

https://www.acmicpc.net/problem/13168 13168번: 내일로 여행 첫 번째 줄에는 한국에 있는 도시의 수 N(1 ≤ N ≤ 100)과 1인당 내일로 티켓의 가격 R(1 ≤ R ≤ 1,000,000)이 주어집니다. 두 번째 줄에는 N개의 도시의 이름이 주어집니다. 도시의 이름은 알파벳 대소 www.acmicpc.net > 풀이 - 문자열 넣으면 인덱스를 주는 name_to_index map을 사용하였다. - 티켓이 있을 때와 없을 때의 그래프를 총 2개 만들었다. - 플로이드 와샬로 'every to every' 최단경로를 구해주었다. 이것을 여행하여 비용을 구하는 로직에서 활용하였다. # -*- coding: utf-8 -*- import sys input = sys.stdi..

https://www.acmicpc.net/problem/14437 14437번: 준오는 심술쟁이!! 첫째 줄에 s(1 ≤ s ≤ 3000)와 둘째 줄에 알파벳 소문자로 이루어진 문제 이름(1 ≤ 길이 ≤ 3000)이 주어진다. 문제 이름에 공백은 없으며, 불가능한 입력(s 접근 위 테이블로부터 DP[문자열 인덱스][지금까지의 변경 횟수]를 정의할 수 있다. 만약 변경 횟수가 각각 [0,1,1,0,0]이라면 다음과 같은 순서를 따른다. 또 고려해야 할 사항이 있는데, 바로 1

https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net > 접근 기본적인 Trie 알고리즘을 구현해놓은 뒤, root부터 시작하는 탐색 함수를 응용해야 했다. 버튼을 누른 총 횟수를 리턴하는 DFS 함수를 토대로 잡았으며 여기에 세부적인 조건이 추가가 되는 식이었다. 먼저 타이핑 횟수를 추가하는 경우는 두 가지로, 단어가 끝나는 경우와 count(insert할 때마다 1씩 증가되는 Node의 멤버 변수)가 1인 경우이다. 전자의 경우에는 결과값에 타이핑 횟..

https://www.acmicpc.net/problem/2560 2560번: 짚신벌레 첫째 줄에 a, b, d, N을 나타내는 네 정수가 빈칸 하나를 사이에 두고 차례로 주어진다. 단, 0＜a＜b＜d ≤ 10,000이고, 1 ≤ N ≤ 1,000,000이다. www.acmicpc.net > 접근 최초에는 [1] -> [0,1] -> [1,0,1] -> [1,1,0,1] -> [1,1,1,0,1] -> [2,1,1,1,0,1] -> [2,2,1,1,1,0] 식으로, 리스트를 right shift 시킨 뒤 a~b 범위의 합을 맨 앞에 추가하는 식으로 시도하였으나 시간 초과가 나왔다. 최적화 할 수 있는 부분은 총 두 가지가 있었다. 첫번째로 리스트를 right shift하고 맨 앞에 원소를 추가하는 작업을..

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net > 접근 먼저 두 좌표가 주어졌을 때 만들어야 하는 다리의 개수를 구하는 함수를 작성해야 하는데, diff_x + diff_y - 1 한 줄로 해결된다. 그 다음 N이 충분히 작으므로 한 대륙과 다른 한 대륙 사이의 거리를 구하면 되리라고 생각했다. 이 때 같은 대륙 간의 거리를 구하게 될 수도 있으므로 구분지어야 할 필요성이 생겼다. 이를 위해 DFS를 통한 '색칠하기'를 수행해준다. 이 때 색칠은 ..

https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net > 풀이 list가 주어졌을 때 이것의 정렬 함수를 먼저 구현해야한다. 이것은 딕셔너리로 0을 제외한 숫자들을 카운트해준 뒤 정렬을 2번 해주면 된다. 이제 도전과제는 C연산이다. 아래와 같은 리스트를 가정해보자. C연산을 해줬을 때 결과는 다음과 같다. [1,2] -> [1,1,2,2] [2,1] -> [1,1,2,2] [3,3] -> [3,2,0,0] 이 때 문제점은 두 가지다. ..