[BOJ] 11월 3주차
BOJ 1720: 타일 코드
Link : https://www.acmicpc.net/problem/1720
solution
2xN 타일을 채우는 점화식은 \(f(n) = f(n-1) + f(n-2)\times 2\)다.
여기서 중복이 되는 경우를 1개씩 없애야 답이 되는데 중복보다는 중복이 되지 않는 케이스를 찾는게 더 쉽다.
중복이 되는 경우를 a, 그렇지 않은 경우를 b라 하면 \(f(n)=a+a+b\)가 되고 이 문제의 답은 \(a+b\)가 된다.
즉, \(a=(f(n)-b)/2\)이므로 답을 정리하면 \((f(n)+b)/2\)가 된다.
n이 홀수면 중복이 발생하지 않는 경우(b, 대칭)는 가운데에 2x1 타일이 1개 있을 때만 존재한다.
그러므로 답은 \((f(n)+f((n-1)/2))/2\)가 된다.
n이 짝수라면 b는 가운데에 1x2타일이 2개 있을 때, 2x2타일이 1개 있을 때 그리고 아무것도 없을 때 존재한다.
말이 조금 이상한데 아무것도 없을 때라는건 고정된 타일이 없을 때를 의미한다.
이 때 답은 \((f(n)+f((n-1)/2)+f((n-2)/2))/2\)가 된다.
BOJ 1126: 같은 탑
Link : https://www.acmicpc.net/problem/1126
solution
dp[i][j] : i-1번까지 탐색, 두 탑의 높이차가 j일 때 큰 탑의 높이
다음 인덱스로 넘어가면서 블럭을 선택할지, 안할지를 선택해야 하는데
선택하지 않는건 이전의 높이(dp[i-1][j])를 가져오면 된다.
선택하는 경우 케이스가 조금 있는데 높은 탑에 쌓기, 낮은 탑에 쌓기가 있고
높은 탑일 경우 이전 케이스에 블럭의 높이를 올리면(더하면) 되며
낮은 탑일 경우 새로 쌓는 블럭의 높이와 높이 차를 의미하는 j와의 대소 관계에 따라 케이스가 2개를 처리해주면 된다.
서로 높이가 같을 때 최댓값을 취해야 하므로 dp[n-1][0]이 답이 된다.
BOJ 17218: 비밀번호 만들기
Link : https://www.acmicpc.net/problem/17218
solution
문자열을 각각 s1, s2라 하면 Longest Common Subsequence를 구하는 점화식은 다음과 같다.
\(if(s1[i]==s2[j]) : dp[i][j] = dp[i-1][j-1] + 1\)
\(else : dp[i][j] = max(dp[i-1][j], dp[i][j-1])\)
위 점화식으로 탐색을 하면서 이전 위치를 route에 기록해 마지막부터 역추적해 나가며 문자열을 완성했다.
BOJ 16236: 아기 상어
Link : https://www.acmicpc.net/problem/16236
solution
고려해야 할 조건이 조금 많은 BFS다. qna에 고통의 흔적이 보이는 문제다.
현재 크기보다 작은 물고기만 먹을 수 있고 같으면 먹을 수는 없지만 이동할 수는 있다.
먹을 수 있는 물고기를 발견했다고 해서 바로 이걸 먹으러 가는게 아니다.
현재 위치에서 먹을 수 있는 물고기들의 후보 중 가장 위쪽이면서 가장 왼쪽에 있는 물고기를 먹어야 한다.
그 물고기를 반환하도록 매 위치에서 BFS를 돌려줬다.
먹은 양, 현재 사이즈, 위치, 움직인 횟수 모두 반영 혹은 초기화를 해줘야한다!
물론 구현 방식을 꼭 위처럼 할 필요는 없다. 본인의 스타일대로 짜서 AC받으면 그게 정답이다.
BOJ 2211: 네트워크 복구
Link : https://www.acmicpc.net/problem/2211
solution
1번 조건에서 서로 다른 두 컴퓨터간에 통신이 가능해야 한다고 했는데, 어떤 컴퓨터든 연결이 돼야 함을 말한다.
그래프 중 트리의 경우 간선이 n-1개지만 모든 노드끼리 연결이 돼있음을 알 수 있다. 즉, 간선은 n-1개가 돼야 한다.
이 때 쓰여야 하는 간선은 1번이 슈퍼 컴퓨터이기 때문에 1번에서 다익스트라를 돌려 찾아야 한다.
dist가 갱신될 때마다 각 노드가 어느 노드로부터 도달했는지를 route에 기록하고 마지막에 출력하면 된다.
BOJ 16500: 문자열 판별
Link : https://www.acmicpc.net/problem/16500
solution
현재 인덱스에서 모든 문자열을 돌려보며 가능한 케이스를 돌려가면 된다.
DP 문제이므로 메모이제이션을 안한다면 TLE를 받는다.
BOJ 11057: 오르막 수
BOJ 2248: 이진수 찾기
Link : https://www.acmicpc.net/problem/2248
solution
솔직히 DP 문제인지 감도 안왔다. kks227님의 글을 참고했다.
이진수로 이루어진 N자리 수 중에서 1의 갯수를 L개 이하로 사용했을 때 K번째 값을 구해야 한다.
바로 K번째 값을 DP로 찾는다고 생각하지 말고 m개 이하의 1을 사용해서 만들 수 있는 n자리의 이진수의 갯수를 DP로 구하자.
1을 선택할지 안할지만 선택하면 되므로 점화식은 다음과 같다.
\(f(n, m) = f(n-1, m) + f(n-1, m-1)\)
이제 K번째 이진수를 구할 차례다. 재귀를 통해서 값을 구해줄텐데 이 때 위에서 구한 값을 이용해야 한다.
다음 차례(n-1번째)에서 1을 사용하는 경우는 f(n-1, m-1), 그렇지 않은 경우는 f(n-1, m)이 된다.
1을 사용하는 경우부터 세면 큰 값부터(1xxxx)세는건데 순번이 오름차순이므로 0을 사용하는 경우를 써야한다.
현재 K번째를 찾아야 하므로, \(K\leq f(n-1, m)\)이면 f(n-1, m)인 케이스에 K번째가 들어있다는 말이므로
현재 위치엔 0을 채우고 그렇지 않은 경우 1을 채우도록 하면 된다.
값이 0일때 1번째라는 점, 자료형은 long long으로 설정해야 하는 점만 유의하면 된다.
BOJ 13700: 완전 범죄
Link : https://www.acmicpc.net/problem/13700
solution
지문을 요약하면 특정 지점을 피해가면서 목표 지점에 도달할 수 있는 최소 횟수를 구해야 한다.
최소 횟수를 구해야 하니 BFS를 이용했다. 구현이 크게 어렵지 않은 문제.
BOJ 2643: 색종이 올려 놓기
Link : https://www.acmicpc.net/problem/2643
solution
색종이를 올려 놓으면서 쌓는데 바로 밑에 있는 색종이가 위에 있는 색종이보다 넓거나 같아야 한다.
브루트 포스로도 답을 찾을 순 있겠지만(TLE) 메모이제이션으로 빠르게 처리할 수 있기 때문에 DP로 풀 수 있다.
색종이는 90도로 회전이 가능하기 때문에
밑에 있는게 A, 위에 있는게 B라면 A의 긴 변과 B의 긴 변을 비교했을 때 A가 B보다 크거나 같아야 한다.
물론 짧은 변끼리 비교해서도 위와 같이 성립해야 B를 A위에 쌓을 수 있다.
f(cur)에서 cur은 가장 위에 있는 색종이를 가리키도록 설정했다.
BOJ 17408: 수열과 쿼리 24
Link : https://www.acmicpc.net/problem/17408
solution
노드마다 구간별 최댓값, 2번째로 큰 값을 가질 수 있도록 세그먼트 트리를 만들어주자.
BOJ 13925: 수열과 쿼리 13
Link : https://www.acmicpc.net/problem/13925
solution
Lazy Propagation 문젠데, 쿼리가 꽤 많다. 특히 2, 3번 쿼리가 까다롭다.
2, 3번 쿼리는 따로 처리해줄 필요없이 업데이트 쿼리 하나에서 한 번에 처리할 수 있는데 아이디어가 필요하다.
kks227님의 글을 참고해서 풀 수 있었는데 구현하는 것도 좀 신경을 써야한다.
일반적인 Lazy에서 쓰는 구간에 더하는 연산은 배열이름이 Lazy, 더하는 값을 val이라 하면 Lazy[node]에 val을 더하고
리프 노드가 아니라면 자식에 val을 물려주고 Lazy[node]를 0으로 초기화해준다.
곱셈도 비슷하지만 조금 다르다. 여기서 이용하는 배열은 Lazy2, 곱하는 값은 val2라 하자.
(트리가 일단 합 세그먼트 트리로 이루어져 있기 때문에) Lazy2[node]에 val2를 더하지 않고 곱해줘야 한다.
그리고 val2는 Lazy2[node]뿐만 아니라 Lazy[node]에도 곱해줘야 한다.
곱해줬을 때 값이 온전히 곱해질 수 있도록 default는 0이 아닌 1이어야 한다.
이렇게 구간에 곱셈까지 하는 연산까지 구현됐다면 준비는 끝났다. 아이디어는 링크를 참고.
위 코드에서는 곱 Lazy가 lazy[][0], 합 Lazy가 lazy[][1]이다.
BOJ 14495: 피보나치 비스무리한 수열
BOJ 2157: 여행
Link : https://www.acmicpc.net/problem/2157
solution
DP 문제.
dp[i][j] : i번 도시까지 이동하면서 얻는 기내식 점수 총 합의 최댓값
BOJ 9413: 제주도 관광
Link : https://www.acmicpc.net/problem/9413
solution
MCMF로 풀었다.
정점을 분리해주고 각 간선의 비용을 1로 설정해주자.
그룹 2개가 이동해야 하니 소스에서 시작점으로의 용량을 2로 설정하자!
최대 비용을 구해야하니 비용은 음수로 설정해줘야 함에 주의.
BOJ 16460: Cupid
Link : https://www.acmicpc.net/problem/16460
solution
내용이 길지만..
조건에 맞는지만 그때그때 체크해서 맞으면 담고 정렬해서 출력하면 된다.
BOJ 16461: 듀얼 채널 VHF 무전기
BOJ 16463: 13일의 금요일
Link : https://www.acmicpc.net/problem/16463
solution
2019년부터 최대 100000년까지만 조사하면 되므로
첫번째 금요일인 2019년 1월 4일부터 7일씩 더해가며 13일 때마다 답을 갱신해주면 된다.
윤년 체크만 잘 해주면 된다. 단순 구현 문제.
BOJ 1949: 우수 마을
Link : https://www.acmicpc.net/problem/1949
solution
트리이므로 루트 노드를 아무거나 잡고 시작한다. (위 코드에서는 1을 루트로 설정)
그리고 인접한 노드를 돌아주면서 해당 마을이 우수 마을일 때만 인구수를 더하고, 그렇지 않으면 더하지 않는다.
물론 DP로 풀어줘야 TLE를 받지 않는다.
규칙 3번때문에 어떻게 구현을 해야하나 걱정했는데 qna를 참고하고나서 납득할 수 있었다.
대충 이해한대로 요약하면 비우수 마을에서는 주변 마을을 비우수 또는 우수 마을로 설정할 수 있는데
어차피 비우수 마을로 설정한다면 인구수를 더하지 않으므로 우수 마을로 선정할 때보다 인구수가 더 적다.
따라서 굳이 3번을 고려해서 더 구현해줄 필요가 없다. 2번 규칙만 고려해주면 된다.
(꼭 비우수로 선정한다고 손해라고 하는건 아닌거 같고 2번 규칙이 적용됐을 때 손해라고 하는 것 같다)
트리 DP 문제는 풀어본 경험이 거의 없어서 볼 때마다 새로운 것 같다..!
익숙해질 때까지 풀어보자!
BOJ 16464: 가주아
Link : https://www.acmicpc.net/problem/16464
solution
홀수는 무조건 가능, 짝수는 2의 n승꼴로 만들어지는 수만 안되고 나머지는 다 가능하다.
처음엔 일일이 써보다가 힘들어서 직접 짜서 돌려보며 규칙을 찾았다(..)
BOJ 16469: 소년 점프
Link : https://www.acmicpc.net/problem/16469
solution
악당 3명에 대해 BFS를 각각의 맵에 돌리면서 특정 위치에 도달하는 최단 거리를 기록한다.
모든 좌표에 대해 악당 3명이 도달한 땅이면 각각의 최단 거리 중 최댓값을 취한다.
위의 값중 최솟값이 곧 세 악당이 모일 때 걸린 시간의 최솟값이 되며 해당되는 땅의 갯수를 세주면 되겠다.
BOJ 16470: A Homogeneous Country
BOJ 16472: 고냥이
Link : https://www.acmicpc.net/problem/16472
solution
처음에 DP 문제인줄 알고 열심히 고민해보다가 답이 안나와서 알고리즘 분류를 봤는데 투 포인터였다(..)
현재 담은 알파벳 중 알파벳 종류를 반환하는 함수 can()을 활용했다.
시간복잡도가 \(O(N\times len)\)이므로 충분히 통과할 수 있겠다 싶어서 제출하니 AC를 받았다!
BOJ 16473: 팰린드롬 만들기
Link : https://www.acmicpc.net/problem/16473
solution
DP 문제다.
팰린드롬의 중간 위치가 주어졌을 때 팰린드롬이 되기 위해 값을 없애는 횟수의 최솟값을 구해야 한다.
없애는 횟수의 최솟값? 이걸 바로 구해보려고 했는데 몇 가지 간단한 반례를 못뚫어서 뒤집어서 생각해봤다.
없애는걸 세지말고 중간값을 기준으로 가장 긴 팰린드롬의 길이를 구하고 전체 길이(n)에서 빼버리면 되지 않을까?
이렇게 생각하니 훨씬 간단하게 풀 수 있었다!
투 포인터처럼 왼쪽, 오른쪽을 가리키도록 설정하고
값이 같다면 +2를 해주고 왼쪽으로 1칸, 오른쪽으로 1칸 이동하고
다르다면 왼쪽으로 1칸 이동 또는 오른쪽으로 1칸 이동하도록 해주면 된다.
BOJ 1695: 팰린드롬 만들기와 같은 문제다. 제목도 같다
다만 이 때는 팰린드롬의 길이가 짝수가 될 수 있음에 주의하자.
BOJ 16475: 수학 미로
Link : https://www.acmicpc.net/problem/16475
solution
함정 지역을 얼마나 지났는지(cnt)를 포함해서 큐에 넣어야 한다.
간선이 역방향으로 바뀔 수 있는 간선인지에 대한 정보도 담아주어야 한다.
또한 2p번 스위치를 누를 때마다 0으로 초기화를 시켜주어야 하며
일반적으로 최단 거리를 구할 때 dist[to]를 사용했다면 이 문제에선 정점을 여러번 거칠 수 있으므로(TC 참고)
cnt 정보도 포함한 dist[to][cnt]를 활용하도록 하자.
댓글남기기