Problem Solving (59) 썸네일형 리스트형 [BOJ] 10067 수열 나누기 문제 링크: https://www.acmicpc.net/problem/10067 문제 요약음이 아닌 정수 $n$개로 이루어진 수열이 있다. 이 수열을 $k+1$개로 나누어야 하는데, 한 번 나눌 때 마다 새로 나누어진 각 부분의 원소의 합을 곱한 것 만큼의 점수를 얻을 수 있다. 이 때 얻을 수 있는 점수의 최댓값과 그 순서를 구하는 문제이다.$2 \leq n \leq 100,000$, $1 \leq k \leq \min(n-1,200)$ 이다. 풀이 과정 가장 먼저 해야 할 관찰은 어느 순서로 수열을 자르던 간에 최종적으로 얻는 점수에는 변함이 없다는 것이다. 만약 어떤 부분을 2번 잘라 3개의 수열로 나누고, 이 수열의 합을 각각 $S_1$, $S_2$, $S_3$ 이라고 하자. 만약 왼쪽을 먼저 자.. [BOJ] 1693 트리 색칠하기 문제 링크: https://www.acmicpc.net/problem/1693문제 요약$n$개의 정점으로 구성된 트리가 있다. 이 트리를 $1$에서 $n$번까지의 색깔로 칠하는데 $k$번 색깔로 칠하는 데는 $k$만큼의 비용이 든다. 인접한 정점을 같은 색으로 칠하지 않으려고 할 때 최소 비용을 구하는 문제이다.풀이 과정이 문제를 푸는 데 가장 핵심적인 아이디어는, 트리를 색칠하는 데 많아 봐야 $\lg n$개의 색깔만이 필요하다는 것이다. 맨 처음에는 직관적으로 이 성질을 생각했는데, 좀 더 생각해보고 증명을 해 볼 수 있었다. 증명은 아래에!만약 트리를 색칠하는 데 필요한 색깔이 생각보다 적다는 것을 알게 되면, 다음과 같은 동적계획법을 생각해 볼 수 있다. $DP[a][c]=$ $a$번째 정점을 색.. [BOJ] 15977 조화로운 행렬 2018 KOI 고등부 3번이다. 정해는 2d segment tree래서 그렇게 짰는데 사실 set+이분탐색이 훨씬 짧고 깔끔하고 빠르고 메모리 사용량도 적다고 한다. 하여튼 "정해"는 첫째 열 기준으로 정렬한 다음 둘째 열과 셋째 열에서 2d segment tree를 이용해서 pair의 LIS를 구해주면 된다. 메모리 사용량이 문제고 $200000 * (lg200000)^2$ 개만큼 노드 잡았더니 MLE 뜨길래 적당히 줄여서 해봤더니 맞았다. 왜 맞는지 진짜 모르겠는데 실제로 돌리면 같은 노드도 여러번 탐색하고 그래서 최악의 경우에도 노드 개수가 많이 넘어가지는 않는다고 한다. 시간은 5초 제한에 낭낭하게 3.7초 나왔다. (...) 시간복잡도는 $O(n lg n^2)$, 공간복잡도도 마찬가지.다시는 .. [BOJ] 11377 열혈강호 3 이분 매칭이 변형된 형태로 나는 에드몬드-카프 알고리즘을 사용해서 풀었다.k명은 일을 하나씩 더 할 수 있다는 조건이 있기 때문에, source를 bridge 역할을 하는 s1과 s2에 연결한 다음 각각의 용량을 n과 k로 해주었다. 따라서 s1이 모든 사람이 하는 하나의 일, s2가 k명이 할 수 있는 추가 작업을 뜻하게 된다. 그리고 s1과 s2를 모두 사람을 표현하는 정점에 용량 1로 이어주고, 마찬가지로 사람과 일 사이에도 문제에서 주어지는 대로 용량 1인 간선을 연결해주었다. 마지막으로 일과 sink에도 용량을 1로 하여 이어주었다. 이렇게 네트워크 모델링을 하면 성공적으로 AC를 받을 수 있다. 네트워크 플로우 넘 어렵다 ㅠㅠ 1234567891011121314151617181920212223.. [BOJ] 7579 앱 나는 사용가능한 최대 cost를 정해두고 0/1 knapsack을 돌리는걸 파라메트릭 서치로 해서 AC를 받았는데 보니까 아무도 이렇게 풀지 않았다 ㅠㅠ 억울해서 소스를 올린다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include using namespace std; int n,m;int arr[105];int cost[105];int cache[105][10005]; int dp(int idx, int remain){ if(idx==(n+1)) return 0; int& ret=cache[idx][remain]; if(ret!=-1) return ret; int ma=dp(id.. [BOJ] 2629 양팔저울 DP 정의는 $DP(i,j)$=i 이하 번호의 추를 사용하여 왼쪽 저울 - 오른쪽 저울의 무게가 j가 되게 할 수 있는가그러면 $DP(i,j)=DP(i+1,j+weight[i]) || DP(i+1,j-weight[i]) || DP(i+1,j)$라는 점화식이 세워짐. 왼쪽에 올리거나, 오른쪽에 올리거나, 아예 올리지 않거나. 간단한 DP problem 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include using namespace std; int f(int x){ return x+60000;} int n,m;int weight[35];int cache[35][120000]; int dp(in.. NYPC 예선 후기 세줄요약1. 머리나쁘고2. 게을러서3. 조짐 이번 NYPC 예선은 내가 공부를 엄청 게을리 하고 있다는 증거를 잔뜩 남겨두고 떠났다. 전체적으로 맞는 풀이인데 구현을 못하거나/반례가 있는 줄 알고 해결하지 못한 문제들이 너무 많았다. 해결하지 못한 문제는 16번 쉴드 생성기, 19번 종이접기, 21번 금 줄 게임, 22번 보라색 영역이다. 점수를 계산해보면 2,135점으로 본선 가기는 그른듯. 다음은 내가 해결한 문제들에 대한 간단한 해설과 소스코드이다. 3. 아이템 구매간단한 일차방정식을 해결하는 문제이다. Naive하게 코딩할 경우 시간복잡도는 선형으로 나온다. 확장 유클리드 알고리즘을 이용해서 로그 시간복잡도로 해결할 수 있을 것 같다는 느낌이 들긴 하는데 그렇게 코딩할 이유는 없으니까 ^^7 12.. [BOJ] 10840 구간 성분 진짜 어이없게 풀었다. 처음에는 해싱인지 모르고 $O(n^3)$에 최적화 생각했는데롤링 해시 구현하기 귀찮아서 그냥 알파벳에 숫자 하나씩 할당해 놓고 다 더한다음에 일치하면 okay라고 판별했다.int 범위 내에서 하니까 충돌나길래 long long 범위까지 늘렸더니 어셉됐다 ㅋㅋㅋㅋㅋㅋ결과적으로는 $O(n^2 lg n) 풀이임. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include #include #include using namespace std; typedef long long ll; ll prime[]={1553543355441,683.. 이전 1 2 3 4 5 6 7 8 다음
