[BOJ] 11월 4주차
BOJ 10573: 증가하는 수
Link : https://www.acmicpc.net/problem/10573
solution
DP 문제다.
자릿수가 끝자리로 갈 수록 단조 증가하도록 하면서 인풋으로 들어오는 값보다 작은 갯수를 구해야 한다.
단조 증가하는 케이스를 세주기 위해 이전 자릿수의 숫자를 prev로 받아주자.
cur은 현재가 몇 자릿수인지를 의미하고, same은 기준값(인풋)과 같은 값을 유지하고 있는지 여부를 말한다.
마지막 자리에 왔을 때를 기저 사례로 설정해주고, 이 때도 same이 1이라면 기준값과 같다는 말이므로 0을 리턴한다.
그 외의 경우는 모든 조건을 만족한다는 말이므로 1을 리턴한다.
문제에 써져있듯이 long long를 자료형으로 써줘야 함에 주의.
BOJ 11568: 민균이의 계략
BOJ 1256: 사전
Link : https://www.acmicpc.net/problem/1256
solution
BOJ 2248: 이진수 찾기와 풀이가 거의 똑같다.
미리 a, z로 만들 수 있는 경우의 수를 만든 후 현재 자릿수 뒤에 만들어질 수 있는 가짓수를 가져와
k와의 비교를 통해 재귀를 돌려주면서 문자열을 완성하는 방법이다.
거의 이 방식으로는 풀어본 적이 없어서 익혀둬야겠다.
이 문제는 어차피 K가 $10^9$가 상한이므로 $10^9+1$등의 상한보다 조금 더 큰 값을 경우의 수의 상한으로 정해놓으면
(즉, 이 값보다 커지지 않도록 설정해 놓는다면) int형으로 충분히 처리가 가능하다.
이런 생각을 풀 때는 하지 못해서 위 코드처럼 long long이 아닌 unsigned long long으로 설정했다.
실제로 long long으로 제출하니 바로 WA를 받았다.
만약 unsigned long long에서 오버플로우가 난다면 위 코드도 WA를 받을거 같다.
반례가 업데이트돼서 재채점으로 WA를 받는다면야(..)
BOJ 2291: Sequence도 같은 문제.
BOJ 3687: 성냥개비
Link : https://www.acmicpc.net/problem/3687
solution
DP 문제이며, 위에서 푼 BOJ 1256: 사전과 접근 방법은 똑같다.
f(n) : n개의 성냥으로 만들 수 있는 가장 긴 숫자의 길이
g(n) : n개의 성냥으로 만들 수 있는 가장 짧은 숫자의 길이
를 반환하도록 설정했고 큰 수는 B_solve(), 작은 수는 S_solve()에서 만들도록 해줬다.
B_solve에서는 숫자 0~9를 탐색하면서 f(n-digit[i])의 최댓값을, 동시에 i의 최댓값 또한 취하도록 했다.
이 때 digit[i]는 숫자 i를 만드는데 필요한 성냥의 수를 말한다.
S_solve에서도 기준을 반대로 설정하고 재귀를 돌리며 값을 만들어나가면 되겠다.
BOJ 4781: 사탕 가게
Link : https://www.acmicpc.net/problem/4781
solution
f(money) : 현재 남은 금액이 money이 있을 때 얻을 수 있는 가장 높은 칼로리
BOJ 18352: 특정 거리의 도시 찾기
BOJ 1162: 도로포장
Link : https://www.acmicpc.net/problem/18352
solution
dist[i][j] : 도로를 j번 포장하고 i번까지 도달할 수 있는 최단 거리
처음에 주어진 기회가 k번이므로 도로를 포장할지 말지 케이스를 분류해서 큐에 넣어주면 된다.
BOJ 2591: 숫자카드
Link : https://www.acmicpc.net/problem/2591
solution
f(cur) : 수의 길이가 cur일 때 가능한 카드의 배열의 수
점화식은 매우 간단하다. 1칸을 뛰거나 2칸을 뛰면 된다.
근데 수가 1~34만 있으므로 이 범위를 벗어나는 경우는 커팅해줘야 한다.
0이 들어올 수 있음에 주의.
BOJ 11444: 피보나치 수 6
BOJ 10282: 해킹
Link : https://www.acmicpc.net/problem/10282
solution
해킹당한 컴퓨터에서 다익스트라를 돌리고 도달할 수 있는 컴퓨터의 갯수, 제일 오래 걸리는 시간을 출력하자.
BOJ 8394: 악수
Link : https://www.acmicpc.net/problem/8394
solution
dp[i][j] : i번째 사람이 이전 사람(i-1)과 악수를 했다면 j는 1, 아니면 0
$dp[i][1] = dp[i-1][0], dp[i][0] = dp[i-1][0] + dp[i-1][1]$
BOJ 14440: 정수 수열
BOJ 15678: 연세워터파크
Link : https://www.acmicpc.net/problem/15678
이 문제는 세그먼트 트리 또는 덱을 이용해 DP로 풀 수 있다.
다음은 세그먼트 트리를 이용한 풀이다.
solution
현재 위치를 i라 할 때, d칸 이전(i-d)에 있는 징검다리부터 직전 징검다리(i-1)에서 i로 넘어올 수 있다.
즉, 구간 $[i-d, i)$에서 넘어올 수 있다는 말인데 여기서 dp[cur]을 다음과 같이 정의해보자.
dp[cur] : cur번 징검다리를 밟았을 때 얻을 수 있는 최대 점수
그럼 $[i-d, i)$에 속하는 모든 징검다리에서 i로 넘어올 수 있으므로 이 범위에 있는 모든 값을
인덱스로 가지는 dp[] 중 최댓값을 취해야 한다. 이 때 세그먼트 트리를 이용해서 $O(logN)$만에 구할 수 있다.
만약 구간 최댓값이 음수라면 dp[i]에 더해줄 필요가 없다. 설명에 나와있듯이 시작점을 임의로 정할 수 있다.
따라서 음수일 때 영향을 받지 않기 위해 0으로 재설정 해주도록 하자. 물론 a[i]는 항상 더해야 한다.
kks227님의 글에 위 풀이를 포함해 덱으로 풀 수 있는 방법도 소개돼 있다.
d칸 이내에 있는 징검다리만 영향을 받는 범위임을 이용해서 front에서 pop을 해주기도 하고
dp[back]이 dp[i]보다 크지 않다면 back에서 pop을 해주는, 양쪽에서 pop을 할 수 있는 덱의 특성을 이용해서
$O(N)$만에 풀 수 있다. dp값을 갱신하는 컨셉은 당연히 같지만 최댓값을 취하는 방식이 다르다.
링크에 너무 잘 설명돼 있으니 까먹으면 다시 참고하기!
BOJ 1585: 경찰
Link : https://www.acmicpc.net/problem/1585
solution
문제 설명에 적힌 조건을 만족하는 경우만 길을 만들어 놓고
MCMF를 2번써서 최소 유량, 최대 유량을 출력하면 된다.
BOJ 1446: 지름길
Link : https://www.acmicpc.net/problem/1446
solution
도착점(D)의 상한선이 10000이므로 노드 하나하나 연결해주면 TLE를 받을 수 있다.
때문에 각 지름길끼리 앞뒤를 이을 수 있다면(대소 비교) 길이만큼 연결해주고
시작점(0)에서 지름길의 시작점을, 지름길의 도착점을 도착점(D)에 길이만큼 연결해주면 된다.
이후 시작점에서 다익스트라를 돌려 dist[D]를 출력.
BOJ 11014: 컨닝 2
Link : https://www.acmicpc.net/problem/11014
solution
현재 위치가 정해졌을 때 컨닝이 가능한 인접한 위치는 4곳이지만
거꾸로 생각해서 컨닝을 받는 위치가 현재 위치라면 컨닝을 하는 인접한 위치는 6곳이 된다.
단, 홀수열은 인접한 열이 없을 가능성이 있으므로 짝수열을 기준으로 한다.
이 때 인접한 칸이 앉을 수 있는 자리라면 연결을 모두 해주면 되며 모든 점에서 이분 매칭을 돌려주자.
최종적으로 (앉을 수 있는 자리의 수) - (이분 매칭 횟수)가 답이 된다.
BOJ 16235: 나무 재테크
Link : https://www.acmicpc.net/problem/16235
solution
단순 구현 문젠데 시간 제한이 꽤나 빡빡하다.
C++로 풀어서 그런지 (물론 파이썬, 자바 등은 보너스 시간이 있지만) 시간 제한에 매달리지 않고 금방 풀 수 있었다.
다만 시간 제한에 왜 걸릴까 생각을 해봤는데 나무가 같은 자리에 여러개가 올 수 있기도 하고
봄일 때 어린 나무부터 양분을 먹기 때문에 그런거 같다. 이 부분때문에 모든 위치에서 정렬을 해줬다.
처음에 우선순위 큐로 풀어보려고 이렇게 저렇게 해보다가 꼬이고 복잡해지고 코드도 더러워 져서(..)
뺐다가 넣었다가를 특정 계절에서 반복하다보니 시간이 2배로 드는 연산이라 그냥 각 위치를 벡터로 바꿨다.
이 부분 외에는 설명따라 충실히 구현해주면 된다.
구현 문젠데 제출이 3만일 정도로 인기가 많아서 뭔가 했더니 삼성 기출문제인거 같다.
BOJ 1719: 택배
Link : https://www.acmicpc.net/problem/1719
solution
다익스트라로 경로를 역추적하는 문제다.
다익스트라를 돌리는 과정 중에 route[next] = cur로 경로를 담아놓으면 어떤 경로로 왔는지 알 수 있다.
BOJ 14496: 그대, 그머가 되어
Link : https://www.acmicpc.net/problem/14496
solution
a->b로 바꾸는데 비용이 1이 든다고 가정하면, 치환 가능한 경우 m가지를 비용 1로 모두 등록한 후
시작점에서 다익스트라를 돌려 도착점까지 도달하는 최단 거리가 곧 최소 횟수가 된다.
약간의 사고 전환이지만, 난이도는 낮다고 볼 수 있겠다.
BOJ 1445: 일요일 아침의 데이트
Link : https://www.acmicpc.net/problem/1445
solution
다익스트라로 상하좌우로 인접한 지역을 각각 연결시켜줘야 한다.
비용이 중요한데, 나같은 경우 쓰레기가 있는 지역은 2500, 쓰레기 인접 지역은 1로 설정했다.
(쓰레기과 인접한 지역을 지나는건 불편하지만 쓰레기가 있는 지역을 지나는건 정말 싫어한다고 언급돼있다)
사전에 쓰레기가 있는 위치에서 상하좌우로 인접한 지역임을 알 수 있도록 ‘n’을 표시해줘서 비용을 입력하기 쉽게 했다.
‘g’, ‘n’이 아닌 지역은 모두 비용을 0으로 설정하면 된다.
‘S’에서 다익스트라를 돌리고 ‘F’에서 ‘S’로 역추적하면서 밟은 땅의 정보를 얻어 답을 갱신해주면 된다.
댓글남기기