ICPC Practice #1. 2014 Pacific Northwest Regional (Div 2.)

(문제 세트) https://www.acmicpc.net/category/808

원래 대회는 5시간짜리인 것 같긴 한데, 그냥 3시간 돌렸습니다. 3시간이 인예 대회 시간이기도 하고..

결과는 상당히 실망스럽긴 한데, 뭐 어쩌겠어요.. 더 연습하겠습니다 ㅠ

 

http://acmicpc-pacnw.org/ProblemSet/2014/html.all/index2.html

찾아보니 원래 대회의 스코어보드도 나오더군요. 5위.. 5위라.. 10솔브는 또 어떻게 한 거지..

 

 

 

 

[문제 풀이]

Div 2 - M번. Polyhedra

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

10569번: 다면체

x = V - E + F = 2라는 식을 주고 있고, 입력으로 V와 E가 들어올테니 F를 출력하라고 합니다. 식을 변형하여 F = 2 - V + E를 얻을 수 있으므로 그대로 구현하면 됩니다.

 

 

 

 

Div 2 - N번. Majority

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

10570번: Favorite Number

어떤 수가 가장 많이 나왔는지, 가장 많이 나온 게 여러 개라면 그 중 가장 작은 수를 출력하면 됩니다. 여러 구현 방법이 있겠지만, 수의 범위가 [1, 1000]으로 좁기 때문에 저는 카운팅 배열을 만들어서 구현(i라는 수가 들어오면 arr[i]의 값을 1 올림)하는 쪽을 택했습니다.

 

 

 

 

Div 2 - O번. Diamonds

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

10571번: 다이아몬드

무게가 높을수록, clarity 값이 작을수록 좋은 다이아몬드라고 합니다. 주어진 다이아몬드 리스트에서 어떤 부분 리스트(부분 수열)가 "점점 더 좋아지는 다이아몬드로 이루어진 부분 리스트"인지를 찾고자 합니다. 이때 이 부분 리스트의 길이는 최장이어야 합니다.

 

$O(N^2)$ LIS를 구할 때와 거의 동일하게 dp로 해결할 수 있습니다. dp식을 다음과 같이 정의해봅시다.

• $dp[i]$ : $i$번째 다이아몬드까지의, 조건을 만족하는 최장 수열 길이

어떤 인덱스 $k$에 대하여 $k$번째 다이아몬드보다 $i$번째 다이아몬드가 더 좋다고 합시다($k < i$). 이때 $dp[i] = dp[k] + 1$이라고 할 수 있습니다. 이런 $k$가 하나만 존재하지 않고, 0부터 $i-1$까지 총 $i$개가 존재하므로 차례대로 순회하면서 $dp[i]$ 값이 최대가 되게끔 갱신해줍니다. 즉 $dp[i]$가 갱신되려면 아래의 세 조건을 만족해야 합니다.

1. $i$번째 다이아몬드의 무게 > $k$번째 다이아몬드의 무게
2. $i$번째 다이아몬드의 clarity < $k$번째 다이아몬드의 clarity
3. $dp[i] < dp[k] + 1$

총 시간복잡도는 $O(N^2)$입니다.

 

 

 

 

Div 2 - T번. Runes

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

10557번: Runes

 

?에 0부터 9까지 직접 넣어보면서 해결해보면 됩니다. 단, ?가 0이 되려면 여러 조건을 만족해야 합니다.

1. 당연히, ?가 0일 때 올바른 계산식이 성립해야 합니다.
2. leading zero가 되는지를 확인합니다. ? 앞에 아무것도 없거나(계산식의 맨 앞이거나), +, -(leading -가 아님), *, =이 있는데, 뒤에 수(0~9)나 ?가 있을 때 leading zero가 됩니다.
3. -0과 같은 식이 되는지를 확인합니다. (연산자 -와 혼동하지 않도록, 계산식을 처음에 훑을 때 미리 연산자의 위치를 저장해두는 것이 좋습니다.) -뒤에 ?가 오는지만 확인하면 됩니다. (물론, 연산자 -는 제외합니다.)

한편 다음의 사항도 주의해야 합니다. "...and it won’t be one of the other given digits in the expression." 문장에 따라 계산식에서 이미 사용된 수는 ?에 사용하지 않도록 합니다.

 

 

 

 

Div 2 - W번. Wormholes

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

10568번: Wormholes

우선 모든 행성 간의 거리를 구해봅시다. 웜홀이 없다고 생각할 때, 행성 간의 최단거리가 항상 두 행성을 직접 잇는 직선 거리가 되는 것은 아닙니다. 다른 행성을 거쳐 목적지 행성에 도착하는 방법도 있기 때문입니다. 이렇게 어떤 경유점을 거쳐 최단거리를 구하기 위해서는 '플로이드 알고리즘'을 사용하면 됩니다. 

 

웜홀이 있는 경우는, 두 행성 간의 거리(양방향이 아닌 단방향)를 0으로 두면 여전히 플로이드 알고리즘을 적용할 수 있습니다. 거리들을 실수형으로 처리한 다음, 출력할 때만 반올림하는 것에 주의합시다.

 

 

 

 

[업솔빙]

(추후 추가 예정)