주간 문제풀이 12 (BOJ 6757 / 2276 / 3321 / 5822)

BOJ 6757 - 팰린드롬 진법

https://www.acmicpc.net/problem/6757

6757번: 팰린드롬 진법

문제: 10진법 숫자 X가 주어졌을 때, b진법으로 나타냈을 때, 팰린드롬인 것의 개수를 구하자. (2 ≤ b < X)

풀이:

b진법으로 나타냈을 때, 자릿수가 두 개인 것과, 자릿수가 세 개 이상인 것을 나눠서 풀자.

자릿수가 두 개인 경우는, 첫 자리와 두번째 자리가 같아야 한다. 두 개의 자리가 모두 a라고 하면, a*b+a = x 라는 식을 만족해야 하고, 가능한 모든 a에 대해서 순회하는 것은 10^5개 이하로 순회할 수 있다.

자릿수가 세 개 이상인 경우는, b가 X^(0.5) 보다 작아야 하기 때문에, 모든 경우를 브루트포스로 순회할 수 있다.

 

http://boj.kr/0fe22fceaecb44b79b53f25557243257

 

 

BOJ 2276 - 물 채우기

https://www.acmicpc.net/problem/2276

2276번: 물 채우기

문제: N*M크기의 물통이 있고, 각 칸의 높이가 다른데, 물통에 물을 부었을 때 담을 수 있는 물의 최대량을 계산하자.

풀이:

각 칸마다 물통 자체의 높이 + 그 위에 있는 물의 높이를 생각해볼 수 있다. 이 높이를 편의상 water[r][c]라고 칭한다. water[r][c] 는 주변 네 개의 칸보다 모두 낮아야 하지만, 물통 높이 자체보다는 낮아질 수 없다. 이 점에서부터 시작해서, 먼저 외곽에 닿아 있는 water[r][c]가 정확히 물통 높이가 되도록 하고, 그 후에는 반복적으로 가장 낮은 water[r][c]에서부터 순서대로 주변의 water값을 자신의 값으로 낮춘다 (물론 물통 높이보다는 낮아지지 않게). 다익스트라와 유사하게 우선순위 큐를 사용해 아직 확인하지 않은 가장 낮은 water[r][c]값을 가지고 있으면 쉽게 풀 수 있다.

 

코드: http://boj.kr/3d6de1bb5fab494bad7e72f10124d0b5

 

참고: https://www.acmicpc.net/problem/15972 와도 비슷한 문제다. ( https://dlwocks31.tistory.com/21 에 풀이)

 

BOJ 3321 - 가장 큰 직사각형

https://www.acmicpc.net/problem/3321

3321번: 가장 큰 직사각형

문제: 0과 1로 이루어진 N * M 행렬이 주어졌을 때, 1로 이루어진 가장 큰 직사각형을 찾는 문제. 이 때, 열의 순서를 바꿀 수 있다.  (N <= 15000, M <= 1500)

 

풀이:

pre[i][j]를 (i, j)위치 아래로 몇 개의 1이 이어져 있는지로 정의할 수 있다. 이 값은 행이 내려감에 따라 1씩 줄어들거나, 0에서 0이 아닌 값으로 늘어나거나 둘 중 한 방식으로 변화한다.

 

이걸 기반으로 만드는 가장 간단한 풀이는: 행을 순차적으로 순회하면서, 각 행에 있는 모든 pre값을 정렬하고, 이를 통해서 해당 행에서 시작하는 직사각형들의 크기를 빠르게 쿼리하는 것이다. (정렬된 pre배열에서 i 원소보다 같거나 큰 건 i개) 다만, 이 풀이는 O(NMlogM) 이라 시간초과가 난다.

 

이 풀이에 대한 개선으로, pre값이 M이하인 경우에는 bucket sort로 정렬하고, M이상일 경우에는 그러한 값들을 따로 정렬된 상태로 조회할 수 있는 multiset을 관리해보자. 해당 multiset에는 각 열의 pre 값이 최대 N / M번만 들어갔다가 나가게 되어서, 기존 풀이의 시간복잡도에 있는 로그를 제거할 수 있다.

최종 시간복잡도는 pre값이 M이하인 경우를 처리하는데 O(NM), pre값에 M이상인 경우의 multiset을 만드는 데 O(NlogM), 해당 multiset을 순회하는 데 O(NM)으로 모두 합쳐서 O(NM)이다.

코드: http://boj.kr/e39701f46f6046039068382a59f69055

 

---

참고 1: 좀 더 일반적인 풀이는 이 글에 있는 풀이인듯 하다. https://blog.naver.com/PostView.naver?blogId=jinhan814&logNo=222544112922&parentCategoryNo=52&categoryNo=11&viewDate=&isShowPopularPosts=false&from=postView 

참고 2: O(N^2)으로도 뚫린다. (https://www.acmicpc.net/source/share/a7b82e2275444622979413aa7d291d3e )  문제가 2009년 문제라서, 그 동안 하드웨어 발전이 많이 된듯..

 

 

 

BOJ 5822 - 악어의 지하 도시

https://www.acmicpc.net/problem/5822

5822번: 악어의 지하 도시

문제: N개의 방을 연결하는 M개의 복도가 있고, 각 복도에는 통과하는데 드는 시간이 있다. N개의 방들 중 K개의 방은 탈출방이다. 목표는 0번째 방에서 아무 탈출방에 도착하는 것인데, 방에서 다른 방으로 이동하기 전에 문지기가 복도 중 임의의 하나를 막을 수 있다. 탈출방에 도착할 수 있는 가장 빠른 시각을 구해야 한다.

 

풀이: 

문지기의 입장에서는 항상 가장 빨리 갈 수 있는 길을 막아서, 탈출자가 두 번째로 빠른 길로 탈출하게 하는 것이 최선이다. 또한, 탈출방에서 시작할 수 있다면 필요한 거리가 0임은 자명하니, 여기서부터 시작해서 다른 노드에서 탈출점으로 가는 최단거리를 하나하나 확정해나가는 방식을 생각해볼 수 있다.

 

탈출점들을 시작점으로 잡고 시작점들에서 다른 점으로 가는 최단 거리를 다익스트라와 비슷하게 구하되, 각 노드에서 첫 번째로 가까운 거리와 두 번째로 가까운 거리를 각각 유지하고, 한 노드에서 다른 노드로 이동할 때는 두 번째로 가까운 거리만 사용하는 방식을 사용하면 모든 노드에 대해 탈출점으로 가는 두 번째로 가까운 거리를 구할 수 있다.

그림으로 그리면 대충 이렇게. 파란색 원은 거리 구하는 순서.

 

주의할 사항은, 이 문제에서의 relax함수는 일반 다익스트라와는 다르게 멱등성이 없게 구현되기 쉽다. 따라서 일반 다익스트라를 구현할 때와 다르게, 임의의 노드에서 인접한 노드로 relax를 수행하는 과정을 노드당 한 번 초과해서 수행하지 않도록 유의하자.

 

코드: http://boj.kr/0389db1ccc8848bd8f94509219498d07