[BOJ] 10월 4주차
인접한 비트의 개수
Link : https://www.acmicpc.net/problem/2698
solution
DP 유형.
a가 문자열의 길이, b가 1이 연속인 횟수, prev를 이전 값이라고 하면 점화식은 다음과 같다.
$if(prev=0): f(a, b, prev) = f(a+1, b, 0) + f(a+1, b, 1)$
$else: f(a, b, prev) = f(a+1, b, 0) + f(a+1, b+1, 1)$
a의 길이가 n이 됐을 때 b가 k라면 1을, 이외에는 0을 리턴하도록 설정해준다.
피보나치 수의 확장
Link : https://www.acmicpc.net/problem/1788
solution
음의 방향으로 피보나치 수열을 확장하는데 일반적인 피보나치 수열에서 약간만 수정해주면 된다.
직접 예를 만들어보면 금방 규칙을 찾을 수 있다.
무한 수열
Link : https://www.acmicpc.net/problem/1351
solution
DP 유형인데 좀 특이하다. N이 \(10^{12}\)까지 커질 수 있다!
가우스는 나머지를 버리기만 하면 돼서 구현이 어렵지 않은데 위처럼 커지는 경우는 처음봐서 당황스러웠다.
결론적으로는 N이 많이 크더라도 거쳐가는 가짓수가 많지 않아 map을 cache로 이용하면 풀 수 있다.
퇴사 2
Link : https://www.acmicpc.net/problem/15486
solution
BOJ 14501: 퇴사에서 범위가 커진 버전이다!
무려 상한선이 10만배나 커진만큼 풀이 방법도 달라졌다. 위에선 브루트 포스로 풀 수 있고 여기선 DP로 풀어야 한다.
위 문제에서 4달 전에 제출했던 코드를 보니 DFS라는걸 안지 며칠 안돼서 고생하며 짰던 생각이 난다.. ㅠㅠ
DP를 몇 문제 연습한 지금은 다행히도 푸는데까지 많은 시간이 들진 않았다!
고려해야 하는 케이스가 현재 일을 선택할지, 안할지 딱 2가지 뿐이다.
현재 인덱스가 cur이라 하고 일에 대한 정보를 a라 하면 점화식은 다음과 같다.
\(f(cur) = max(f(cur+a[cur].day)+a[cur].price, f(cur+1))\)
돌 게임 4
Link : https://www.acmicpc.net/problem/9658
solution
개인적으로 이런 종류의 문제가 좀 까다롭다고 생각한다.
설명에 ‘두 사람이 완벽하게 게임을 했을 때’라는 말 때문에 조건을 정하기가 매우 까다로웠다.
현재 남은 돌의 갯수를 cur, 누구 차례인지를 나타내는걸 who로 설정해놓고 DP로 풀었다.
벽장문의 이동
Link : https://www.acmicpc.net/problem/2666
solution
DP 유형.
2곳을 제외한 나머지는 모두 닫혀있고 만약 닫힌 쪽을 열려면 열린쪽으로 블럭을 밀어야 한다.
블럭을 이동해 열렸던 곳이 닫히면 닫혔던 곳이 열리므로 항상 2곳만 열린 상태로 남게 된다.
따라서 열린 2곳의 인덱스(a, b)를 인자로 갖고 현재 턴을 cur이라 하면 점화식은 다음과 같다.
arr[i]는 i번째일 때 열려고 하는 대상의 인덱스이다.
\(f(cur, a, b) = min(f(cur+1, arr[cur], b)+|arr[cur]-a|, f(cur+1, a, arr[cur])+|arr[cur]-b|)\)
파스타
Link : https://www.acmicpc.net/problem/5546
solution
DP 유형. 연속해서 같은 메뉴를 먹는 날이 3일이 되지 않도록 값을 갱신해주면 된다.
fix[i]는 i번째 날에 먹는 메뉴의 종류를 의미하도록 설정했다.
처음에 풀 때 지정된 메뉴가 있으면 3번 연속 같은걸 먹어도 상관없도록 했는데 이러면 TC에서도 틀린다.
지정된 경우에도 정해진 조건을 따르도록 처리해줘야 한다.
현재 날짜를 day, 직전에 먹은 메뉴를 prev, 연속해서 먹은 횟수를 cnt로 설정했다.
Boggle
Link : https://www.acmicpc.net/problem/9202
solution
트라이 알고리즘 + DFS로 풀었다.
단어들을 트라이에 집어넣으면서 끝나는 위치마다 어떤 단어가 끝나는지 입력받은 순서를 인덱스로 이용해 구분했다.
같은 단어를 여러 번 찾으면 한 번 찾은 것으로 세기때문에 chk[]를 이용했으며, 이것 또한 위의 인덱스를 이용했고
가장 긴 단어가 여러개일 경우 사전 순으로 앞선 것을 취하는건 min()으로 처리했다.
단어가 AB, ABAB로 나왔을 경우 AB, ABAB모두 잘 나오는지 꼭 체크해보기.
이 부분을 잘못 처리했어서 수정하니 AC를 받을 수 있었다.
반도체 설계
Link : https://www.acmicpc.net/problem/2352
solution
LIS 알고리즘을 \(O(n^2)\)로 하는 방법밖에 몰랐었는데 \(O(nlogn)\)만에 처리하는 방법을 알게됐다!
전자는 DP를 이용한 풀이라면 후자는 이진 탐색을 통해 처리하게 된다.
BOJ 1365: 꼬인 전깃줄과 동일한 문제.
게임
Link : https://www.acmicpc.net/problem/1103
solution
DP + DFS 유형.
사이클을 도는지 여부에 따라 -1을 출력해야 한다. 이 부분을 체크하는게 제일 어려웠다.
지나온 길을 모두 route에 담아주면서 계속 길을 돌다가 이미 지났던 위치 (x, y)에 도달했다고 하자.
(x, y)는 지났던 길이므로 cache[x][y] != -1이다. 따라서 if(ret != -1)로 들어가게 된다.
이미 지났던 길이라면 route에 (x, y)이 있다는 말이므로 모든 route[i]를 사이클(cycle[x][y])로 지정해준다.
만약 지났던 길이 아닌데 if(ret != -1)로 들어갔다면 ret을 리턴해주면 된다. (메모이제이션)
나처럼 (0, 0)을 시작으로 짰다면 f(0, 0)로 들어가기 전에 route에 (0, 0)을 먼저 넣어주고 시작해야 한다.
전깃줄 - 2
Link : https://www.acmicpc.net/problem/2568
solution
위에서 풀었던 BOJ 2352: 반도체 설계에서 수열까지 출력해야하는 문제다.
수열을 출력하지 않는다면 코드는 굉장히 간단해지지만, 그렇지 않은 경우 코드가 좀 더 길어진다..!
LIS를 찾는 과정 중에 현재 값이 담겨있는 마지막 값(target[cnt])보다 크든 작든 (인덱스, 값)을 스택 tmp에 담아준다.
그리고 for문이 끝났다면 tmp를 top부터 처리해준다. 이 때 cnt는 LIS의 길이가 된다!
끝에서부터 출발해 처음 원소까지 탐색해 나가면서 cnt와 담았던 인덱스(tmp.top().first)가 같으면 order에 담고
cnt가 0이 돼서 모두 처리가 됐다면 order의 순서를 뒤집어주면(reverse) LIS를 구할 수 있다.
이 문제에서는 전깃줄이 오른쪽에 닿는 부분으로부터 시작점으로 바꿔줘야 하기 때문에 위 설명이 코드와 좀 다르다.
맨 처음에 LIS 길이를 구하는데 \(O(nlogn)\)이 걸리고 나머지는 모두 \(O(n)\) 이므로
최종적으로 \(O(nlogn)\)만에 답을 구할 수 있게 된다.
BOJ 2550: 전구도 전깃줄 - 2와 같은 문젠데 n의 범위가 좀 작다.
수열과 쿼리 16
Link : https://www.acmicpc.net/problem/14428
solution
세그먼트 트리로 풀 수 있다.
최솟값을 출력하는 세그먼트 트리에서 한 단계 더 나아간 문제다. 최솟값이 위치한 인덱스를 출력해야 한다.
때문에 트리를 하나 더 만들어서(indextree) 자식 노드끼리 누가 더 작은지에 따라 indextree를 업데이트 해줬다.
2번 쿼리는 구간 [i, j]에서 탐색해야 하는데 실제로 누가 최솟값인지 알아야하고 동시에 인덱스가 뭔지 알아야 해서
pair<ll, ll>로 반환하도록 설정해줬다. 첫 번째는 인덱스를, 두 번째는 값을 의미한다.
BOJ 14427: 수열과 쿼리 15는 2번 쿼리가 [i, j]가 아닌 전체를 대상으로 한다.
첫 번째 인덱스(indextree[1])를 반환하도록 바꿔주면 된다. 사실상 둘 다 같은 문제.
사탕상자
Link : https://www.acmicpc.net/problem/2243
solution
BOJ 12899: 데이터 구조와 같은 문제.
풀이 : https://yooniversal.github.io/blog/post81/
댓글남기기