hjhj97

[BOJ 2568]전깃줄-2 알고리즘 분류상으로 LIS로 되어있기 때문에 어렵지 않게 풀기는 했다만, 만약 분류를 모른 상태로 접했다면 어떻게 풀어야 할지 고생했을 문제이다. 이런 부류의 문제를 풀 때는 어떻게 LIS로 푸느냐 보다는, 왜 이 문제가 LIS로 풀릴 수 있는지를 파악하는 것이 더 중요하다. 전깃줄1 문제도 있는데, 없애야 할 전선의 최소 개수를 구하는 것은 같지만 2는 거기서 구체적으로 몇 번째의 전선을 없애야 하는지를 더 구해야한다. 게다가 N이 최대 10만으로 늘어났기 때문에 LIS를 구하는 알고리즘도 O(NlogN)만에 구해야 한다. 사실 구하는 법을 까먹어서 예전 소스를 슬쩍 보고왔다. 우선 왜 이 문제가 LIS에 해당하는지부터 알아보자. 이 문제에서 핵심은 전선끼리 교차하는 경우가..

[BOJ]2662-기업투자 예전부터 시도해왔던 문제인데 이제서야 풀었다. 전형적인 dp문제로, 각 기업별로 투자금별 수익금이 제시되고 한정된 금액으로 최대의 수익을 내기 위해서 어느 기업에 얼마만큼 투자를 해야하는지 묻는 문제이다. dp테이블의 의미는 dp[a][b]=c -> 금액 a원을 b번째 기업까지 투자했을 때 만들 수 있는 최대 금액 c원이다. 나 같은 경우에 최대 수익금을 찾는 구현은 그럭저럭 잘 했으나 각 기업에 얼마만큼 투자를 했는지 찾는 과정의 구현이 조금 애를 먹었다. dp loop를 돌리는 동안에 별도로 add[][]라는 배열을 마련해서 이전 상태에서 현재상태의 얼마를 더 투자해서 현재의 금액이 되었는지를 저장하는 역할이다. 그리고 최대 금액을 알아낸 상태에서 역순으로 금액을 빼가면서 ..

[BOJ]13302-리조트 dp테이블의 의미는 dp[a][b]=c라고 했을 때 'a번째 날까지 쿠폰 b개가 존재하기 위해서 필요한 최소 금액 c' 이다. 쿠폰 3개를 하루 이용권으로 교환할 수 있기 때문에 따로 처리를 해주어야 한다. 이는 28~31번째 줄에 나와있다. 처음에는 쿠폰이 3장 이상 모이자마자 사용할 수 있다고 처리해서 틀렸다. 실제로는 3장 이상을 모은 다음 날부터 사용이 가능하다. 예를 들어 [3일권][5일권]을 선택했을 때, 25000+37000-10000으로 계산했다. 왜냐하면 dp배열 상으로는 dp[8][3]이 되므로 마지막 처리에서 dp[8][3]=c -> dp[8][0]=c-10000으로 계산하는 논리였기 때문이다. 실제로는 dp[8][3]=c -> dp[9][0]=c가 되어야 ..

1100B-Build a contest B번 난이도 치고는 조금 고민해볼 문제였다. 문제는 총 1~n까지 총 n개 종류의 수가 m개 주어진다. 여기서 1~n까지의 숫자가 모두 등장할 때마다 1을 출력하고 그렇지 않을 때는 0을 출력하는 문제다. 만약 모두 등장했다면 다시 1~n까지의 등장 횟수를 모두 1씩 차감해주어야 한다. 가장 naive한 풀이는 매 숫자가 들어올 때마다 1~n까지의 숫자가 모두 유효한지를 검증해보는 것인데, 그러면 시간복잡도는 O(N*M)이다. 이 문제에서 n,m은 최대 10만이므로 이 풀이는 불가능하다. 핵심은 각 시행에서 1~n까지의 숫자가 모두 등장했는지를 어떻게 하면 빠르게 확인하느냐이다. 이 과정을 O(N)보다 빨리 수행하여야 한다. 나는 이를 위해서 cur라는 변수를 추가..

[Codeforces]1102D-Balanced Ternary String 구현력이 얼마나 중요한지 일깨워 주는 문제. 길이가 3의 배수이고 오직 0,1,2로만 이루어진 문자열이 주어진다. 이 문자열에서 등장하는 0,1,2의 빈도는 3개 모두 같도록 만들기 위해서 각 문자를 replace할 수 있는데, 이 때 replace 횟수가 최소가 되도록 하면서 동시에 사전순으로 가장 앞에 있는 문자열을 구하는 문제이다. 문제 난이도는 D번 치고 그렇게 어렵지는 않고, 실제로 이 문제를 접했을 때 솔루션도 금방 나왔다. 0,1,2의 등장 횟수가 n/3이 되도록 맞춰주기 위해서 많이 등장한 숫자는 적게 등장한 숫자에게 자신의 자리를 양보해주는 식이다. 그러면서 사전순 정렬도 고려해야 하기 때문에, 0이 제일 먼저 나..

15673-헤븐스 키친 2 N개의 수들이 주어지고, 이 N개의 수들을 2개로 그룹지어서 2개의 그룹의 곱이 최대가 되도록 만들면 된다. (그룹의 가중치 = 그룹에 속한 수들의 합)N=10만이므로, N^2 풀이는 당연히 불가능하다. 우선 테스트케이스에서 99가 나오는 원리이다. 1,2,3 번째에서 -11, 5번째에서 -9를 선택하면 곱이 99가 되고, 이 값이 최대이다. l_max[],l_min[]배열은 왼쪽부터 보면서 누적합을 계산해 나간다. 여기서 max[]배열은 양수만 고려하므로 만약 누적합이 0보다 작아진다면 차라리 그 수를 선택하지 않는것이 더 나은 선택이므로 0이 된다. min[]배열 또한 같은 원리로 누적합이 0보다 커진다면 그냥 0으로 둔다. 그리고 maxS는 이러한 max 배열들 중에서 지..

15668-방 번호 아이디어성이 짙은 문제이다. N=10억이기 때문에 당연히 전탐색은 불가능하다. 그래서 반드시 N을 다 보지 않고도 풀 수 있는 방법이 있을 것이라고 생각했다. 풀이를 말로 설명하기는 참 어려운 문제이다.결론부터 얘기하자면, 단 43210까지만 봐도 모든 경우를 처리할 수 있다. i=1~43210까지의 반복문에서 i와 N-i 의 값을 구해서 그 두 값에서 겹치는 수가 있는지만 확인해주면 된다. 예를 들어, N=100 일 때를 생각해보자. i=1 때는 N-i(=k라고 하자)=99가 되고 k 자체에서 9가 두 번 사용되므로 탈락이다. i=2 때는 k=98이고 모든 수가 한 번 씩만 사용되었으므로 가능하다. 그래서 i=1~43210까지 하나라도 가능한 케이스가 있다면 출력하고, 모두 불가능하..

1095C-Powers of Two 어떤 수 n이 주어지면 그 수를 총 k개의 2의 거듭제곱수(1,2,4,8...)의 합으로 표현할 수 있는지, 가능하다면 그 조합을 출력하는 문제이다. 콘테스트 당시에는 dfs를 이용해서 풀어보려고 했으나, n=10억, k=20만이기 때문에 당연히 시간이 터진다. 그래서 왠지 dp적인 기법이 섞으면 되지 않을까 고민하다가 결국은 못 풀었다. 결론부터 얘기하면 dp가 아닌 다른 방법으로도 풀 수 있다. 만약 이 문제에서 k가 최소가 되도록 하는 문제였다면 그나마 쉽게 생각할 수 있었을 것이다. k의 최소는 엄청나게 큰 2의 거듭제곱 수부터 시작해서 대소 비교를 하면서 n에서 그 값을 뺄 수 있으면 빼고 아니면 2로 나눠가는 (마치 LCA처럼) 기법을 쓰면 k의 최소값을 구..