2022 알고리즘 탐구반 #7

계획

 

앞으로의 방향을 계획하고, 적당히 쉬운 문제를 얼마나 빨리 풀 수 있을지 알아보기 위해 골드 3문제를 준비해봤다.

 

A. 2225 합분해

2차원 DP로 해결해주면 된다. d[i][j] = i개의 수를 더해 합이 j가 되는 경우의 수

DP 테이블을 채우는 데 시간이 걸려서 총 O(K*N*N)정도이다.

 

B. 2206 벽 부수고 이동하기

일반적인 BFS에 벽을 깬 적이 있다/없다를 표현하는 상태값 하나만 추가하면 O(2 * N * M)으로 해결.

 

C. 10775 공항

계절학교 처음반 여름학교에서 풀었던 문제인데, 세그트리나 union find처럼 하거나 등등 여러 방법으로 풀 수 있다.

이 중 가장 쉬운 방법은 set으로 푸는 것인것 같다.

우선 비행기가 도킹할 수 있는 구간이 [1, g_i]이기 때문에 항상 비행기가 도킹할 수 있는 게이트 중 번호가 가장 큰 게이트에 도킹하는 것이 최적임은 자명하다.

이를 빠른 시간내에 처리해 주기 위해 set에 1부터 G까지 넣어놓고 비행기가 하나 올때마다 비행기가 도킹할 수 있는 구간에 포함되는 가장 큰 수를 찾아주면 된다. 만약 그러한 수가 없다면 비행기가 도킹할 수 없으므로 종료하면 되고, 그렇지 않다면 set에서 그 수를 뽑아낸 후 이 작업을 계속하면 된다.

---

결과

C번은 조금 어려울 수 있다고 생각했지만 A, B는 쉽다고 생각했었다.

그런데 생각보다 잘 못 풀어서 다음에는 문제를 조금 더 쉬운걸로 가져와야겠다.

 

아직 생각하는게 좀 느린 것 같아서 다음에는 DP를 집중적으로 연습하고, 그 다음에는 그래프를 하고...이런 방식으로 진행해야겠다.

 

풀이 준비를 좀 더 제대로 했었어야 했는데 쉬운 문제이기도 하고 졸려서 대충 보고 갔더니 설명을 깔끔하게 못한 것 같다. 다음에는 풀이를 한번이라도 써보고 가야겠다.

 

후배 중 한명이 A번을 어떻게 푸는지 전혀 모르겠다고 해서 경우의 수 문제를 푸는 방법에는 경우를 하나하나 세기, 수학적으로 풀기(팩토리얼, 컴비네이션,,등등), DP로 풀기 이렇게 3가지가 있고, 여기서 하나하나 세는 방법은 경우의 수에 시간복잡도가 비례하기 때문에 이 문제에서는 시간초과가 날 것이고, 수학적으로는 사실 하모니(중복조합)를 사용하면 될 것 같긴 한데 그때는 문제를 잠깐 착각해서 너무 복잡해서 못 풀 것이라고 했다. 근데 어차피 답을 10억으로 나눈 나머지를 출력해야 되는데, 이럴려면 인버스 구해줘야 되고, 이럴려면 또 페르마의 소정리 얘기도 해야돼서... DP로 푸는거라고 했다.

근데 10억으로 나누는 것 때문에 문제를 어떻게 풀어야 될지 몰랐을거라는 생각도 지금 들었다.