파게로그

문제 링크: 1146번 지그재그 서기 https://www.acmicpc.net/problem/1146 가장 나이브하게 풀면 어떻게 될까? 어떤 숫자가 몇 번째 줄에 위치한다는 것을 정한 상태에서, 다른 숫자의 사용 여부를 저장해둔 다음 안 쓴 숫자 중 하나를 골라서 다음 줄의 상태를 탐색해나갈 수 있다. 여기서 조금 더 개선해보면, 자신보다 작은 숫자와 큰 숫자를 각각 별도로 가지고 있으면 편할 것이다. 여기서 조금 더 생각해보면, 숫자 자체는 의미가 없고 숫자끼리의 대소 관계에만 의미가 있음에 착안하여 알고리즘을 개선할 수 있다. 위와 같은 사고 과정을 거치는 것이 이상적이긴 하며, 실제로는, (다행히?) DP로 풀어야겠다는 생각이 먼저 들기는 했다. N

문제 링크: 2229번 조 짜기 https://www.acmicpc.net/problem/2229 1000 이하라는 N의 범위를 고려할 때 O(N2) 알고리즘이 떠오를 법하지만, O(N)으로도 풀 수 있는 문제이다. 일단 학생의 순서를 바꿀 수 없는 상태에서 조를 나누는 것이라는 점에 착안하여, 고려 대상 학생을 한 명씩 추가해나가면서 해당 학생을 ①마지막으로 만든 기존의 조에 포함시킬지, ②이전 학생과 함께 새로운 조를 만들지를 나누어 DP를 적용시킬 수 있다. 다만, 이 문제를 처음 읽으면 다음과 같은 생각을 할 수 있다. "한 조 내에서 최솟값과 최댓값의 차이만을 고려할 것이니, 3명 이상이 하나의 조를 이루는 것은 비효율적이다". 결론부터 말하자면 거짓이다. 당장 1, 2, 3의 예시만 생각해보더..

문제 링크: 11967번 제목 https://www.acmicpc.net/problem/11967 이 문제에서, 구현을 어렵게 하는 케이스는 다음과 같은 경우이다. 위 예시의 경우 곧바로 알 수 있는 것은, ㄴ자 모양을 따라 쭉 불을 켜면서 이동하게 된다는 것이다. 그런데, (3, 4)에는 (4, 0)을 켜는 스위치가 있으며, 우리는 (3, 1) 또한 방문하기 때문에 (4, 0) 또한 방문해야 한다. 하지만 단순 BFS로 문제를 해결하고자 한다면 이미 불이 켜지지 않아 방문할 수 없는 방으로 처리되고 만다. 이를 해결하기 위해서는... 첫 번째로 다음과 같은 무식한? 무지막지한? 방법을 사용할 수 있다. 계속해서 (0, 0)에서 출발해서 BFS를 돌리면서, 이전 탐색과 현재 탐색에서 방문하는 방의 개수가..

문제 링크: 12931번 두 배 더하기 https://www.acmicpc.net/problem/12931 전형적인 DP 문제라고 생각했는데 그리디한 접근이 필요한 문제였다. 내가 헷갈렸던 것은... 어떤 양의 정수를 0으로 만들고자 할 때, 2로 나누는 편이 1을 빼는 편보다 무조건 더 빠른가에 대한 대답이었는데, 이에 대한 답은 '그렇다'이다. 헷갈릴 일이 없는 건데... 아마도 1을 더하는 연산도 있는 경우를 두고 이상한 데서 고민한 것 같다. 참고로 1을 더하는 연산이 있다면, 15 → 16 → 8 → 4 → 2 → 1 → 0이 15 → 14 → 7 → 6 → 3 → 2 → 1 → 0보다 빠르다. 먼저, 양의 정수들에 대해서, 0으로 만들기 위한 횟수를 미리 구해두어야 하는데, 단순히 횟수가 아니..

문제 링크: 22115번 창영이와 커피 https://www.acmicpc.net/problem/22115 처음의 접근 먼저 2차원 DP로 접근하여, 카페인을 K만큼 섭취할 수 있는지부터 확인하고, 별도의 테이블을 통해서 최소 커피 개수를 구해주었다. 1차 개선 생각해보면, 카페인을 K만큼 섭취할 수 있는지의 가능 여부와 최소 커피 개수를 따로 구할 필요가 없다. 최소 커피 개수를 구하는 과정 자체가 가능 여부를 구하는 과정을 포함하기 때문이다. [0, i]의 커피를 고려한다고 할 때, i를 증가시켜나가면서 i번째 커피를 포함시키지 않을 때(dp[j])와 i번째 커피를 포함시킬 때(dp[j - a[i]] + 1) 중 최소 커피 개수를 이용한다. 2차 개선 1차원 DP 배열을 통해서도 문제를 해결할 수 있..

문제 링크: 11049번 행렬 곱셈 순서 https://www.acmicpc.net/problem/11049 일단 고등학교 때 배운, 행렬에 대한 간단한 성질들을 미리 적어둔다... 1. 행렬의 곱셈 연산은 교환법칙이 성립하지 않는다. 2. n×m 행렬과 m×l 행렬에 대한 곱셈 연산을 수행하면 그 결과는 n×l 행렬이다. → n×m 행렬과, m×l 행렬과, ..., l×k 행렬에 대한 곱셈 연산을 수행하면 그 결과는 n×k 행렬이다. 3. n×m 행렬과 m×l행렬에 대해 곱셈 연산을 수행하는 데에 필요한 연산의 수는 n×m×l이다. → A×B = C라 할 때 C00 하나를 구하기 위해 A00B00 + A01B10 + A02B20 + ... + A0mBm0의 계산(m번)을 수행해야 하며 C의 원소는 n×..

문제 링크: 1520번 제목 https://www.acmicpc.net/problem/1520 언젠가 굉장히 무난하게 풀었던 문제인데, 이번엔 굉장히 어렵게 풀었다. 일단 다음에 다시 풀 때에는, 다른 방식으로도 풀어볼 예정이다(https://hoondev.tistory.com/81). 결론을 요약하면 다음과 같다. P(i, j)를 (i, j)로부터 목적지까지 가는 경로의 개수라고 하면, P(i, j) = sum( { P(a, b) | (a,b)는 (i, j)와 인접 & (a, b)는 (i, j)보다 고도가 낮음 } ) 아래 코드에서 dp[i][j]에는 (i,j)에서 목적지까지 가는 경로의 개수를 저장하며, func(i, j)는 dp(i, j)를 채우는 함수이다. 간단하게만 따라가보자. 일단 여기서는 (..

문제 링크: 1188번 음식 평론가 https://www.acmicpc.net/problem/1188 풀이 과정보다, 풀이 과정을 떠올리는 과정을 먼저 설명해보면, 결국 어떻게 나누어지는지 실제로 몇 가지 예를 들어보는 편이 가장 빠른 것 같다. 적어도 민간인 머리를 가진 나에게는 말이다. 생긴 것부터 정수론 문제인 만큼, n > m일 때와 n < m일 때, 그리고 n % m == 0인지의 여부 등을 따져 몇 가지를 고려해보니 반례도 한 번에 고려할 수 있었다. 14라인 일단, 그냥 나누어주면 끝나는 경우에는 한 번도 자를 필요가 없다. 이는 빵이 사람의 배수인 것을 말하고, 물론 사람이 1명인 경우도 포함된다. 18라인 그리고 빵이 사람보다 많은 경우에는, 일단 나누지 않고 온전히 줄 수 있는 빵을 먼..