Round 172

시도했던 문제

- D. 초콜릿 피라미드 https://www.acmicpc.net/problem/25793

- E. 프린트 전달 https://www.acmicpc.net/problem/23887

 

초콜릿 피라미드

수학... 문제였다.

한 층을 채운다고 하면 아래와 같이 식을 세울 수 있다.

w: r * c + (r - 1) * (c - 1)

b: (r - 1) * c + r * (c - 1)

 

식을 조금 더 정리하면 이렇게 된다. 

w: 2 * r * c - (r + c) + 1

b: 2 * r * c - (r + c)

 

고민해봐야 할 부분은 여러 층을 쌓아야 하는데...

예시의 2 * 3을 들면 (2 * 3) + (1 * 2)를 해야 하고,

9 * 3인 경우 (9 * 3) + (8 * 2) + (7 * 1)을 해야 했다.

 

시도1

가장 간단한 방법은 한 층씩 계산해서 더하면 되는데 시간복잡도가 t * c를 하면 엄청 큰 수가 나와서 실패할 것 같았다. 

 

시도2

일단 w와 b는 c만큼 차이나므로 b를 기준으로 구한 뒤 마지막에 c를 더해주면 된다. 

그리고 r과 c는 교환법칙이 성립해서 r을 큰 수로 두고 c를 작은 수로 두었다.

 

시간복잡도를 줄이기 위해 어떻게 하느냐.......

2 * r * c - (r + c)

2 * (r-1) * (c-1) - (r - 1 + c - 1)

2 * (r-2) * (c-2) - (r - 2 + c - 2)

 

- (r + c)

이 부분은 n부터 1까지의 합 공식인 n * (n + 1) / 2를 사용하면 될 것 같았다. 

r은 (r의 합) - (r-c의 합) 이 되고 c는 (c의 합)으로 구할 수 있다.

 

2 * r * c

그런데 이 부분은...! 어떻게 해야 할지 도저히 모르겠다.

2 * r * c + 2 * (r-1) * (c-1) + 2 * (r-2) * (c-2)

이것들의 합을 어떻게 구해야 하지?

처음에는 2 * (r의합) * (c의합) 인줄 알았는데 아니었다...

 

고등수학 다 까먹어서 하나도 기억이 안 난다...

 

시도2

혹시나 t * c를 해도 시간복잡도가 안 터지지 않을까 싶었다.

10의 얼마였는지 사실 기억이 안 났다. 그래서 한 층씩 계산하도록 하고 제출했더니 시간복잡도가 터졌다..

확인해보니 10^9 정도까지 버틸 수 있었다. 

 

프린트 전달

으음.. 문제 보니 bfs 문제이긴 한데 프린트 수를 어떻게 해야 할지 막혔다. 

노드를 건널 때마다 부모 노드의 프린트 개수를 증가시켜줘야 하는데 이걸 어떻게 하지?

번호 작은 거는 프린트 받을 때마다 번호를 기록해두고, 작은 번호로 갱신시키면 되는데 또 부모도 변경해줘야 하잖아.

 

막혔다... 생각이 안 난다....

 

업솔빙

- D. 초콜릿 피라미드 https://www.acmicpc.net/problem/25793

- E. 프린트 전달 https://www.acmicpc.net/problem/23887

 

초콜릿 피라미드

2 * r * c + 2 * (r-1) * (c-1) + 2 * (r-2) * (c-2)

이 부분의 숫자를 k로 치환한다.

k: 층 수라고 한다면

 2 * (r - k + 1) * (c - k + 1) 이라고 표현할 수 있다.

 

이걸 풀어서 정리한 다음에 합을 더하면 된다

 

프린트 전달

bfs + dfs .....