USACO 2017 Jan 전체 풀이

USACO 2017 January Contest에 대한 전체 풀이를 작성하려고 한다. Bronze ~Gold 까지는 전부 작성하고 Platinum은 되는대로 추가할 예정이다.

백준에서는 https://www.acmicpc.net/category/395에서 볼 수 있다.

Bronze 1

BOJ 14455 Don't Be Last

문제 설명: 우유를 얻은 소와 양이 여러차례에 걸쳐 주어질 때 마지막에서 두번째로 적은 양의 우유를 얻은 소를 구하시오. 

문제 풀이: 구조체등을 이용하여 이름과 우유의 양을 같이 저장하자. 이름에 맞춰 짠 우유의 양을 더해주고, 정렬을 해서 출력하면 된다.

여담: 다른 브론즈 문제보다 오히려 어려웠다. 구현과정에서 고려해야 할 것이 적지 않고 은근히 까다로운 문제.

Bronze 2

BOJ 14456 Hoof,Paper,Scissors

문제 설명: 1,2,3에 가위,바위,보를 잘 부여해 1번 플레이어가 최대한 이길 수 있도록 하시오.

문제 풀이: 각각 두 수를 a,b라고 할때, (a%3)+1==b 인 횟수와 (b%3)+1==a 인 횟수를 세서 더 높은 쪽이 답이 된다.

Bronze 3

BOJ 14457 Cow Tipping

문제 설명 : 왼쪽 윗 칸을 포함한 직사각형을 뒤집어서 모든 칸을 다 0으로 만드는데 걸리는 최소 횟수를 출력하시오.

문제 풀이: 맨 오른쪽 아래칸은 전체 직사각형으로 밖에 뒤집을 수 없다. 그 칸을 고정시키고 나면 그 바로 왼쪽 칸도 그 칸을 포함한 직사각형으로 뒤집을 수 밖에 없다. 이런식으로 가장 구석칸부터 차례대로 이 칸을 뒤집어야하는지를 확인하고, 뒤집어야 하면 naive하게 뒤집어 주면 된다. 시간복잡도는 O(n^4).

Silver 1

BOJ 14452 Cow Dance Show

문제 설명 : 각 소들이 춤을 추는 시간이 주어진다. 한 스테이지에는 한번에 한 마리의 소만 춤을 출 수 있다. 모든 소가 스테이지에서 시간 T안에 춤을 추기 위한 스테이지의 최소 갯수를 구하시오.

문제 풀이 : 만약 스테이지 갯수가 k일때 가능하면 k이상일 때 항상 가능하고 k일때 불가능 하면 k이하일때 항상 불가능하므로, 이분탐색을 이용하여 문제를 해결 할 수 있다. 스테이지 갯수를 고정시켜놓고, 소들을 춤추는 시간에 대해서 정렬한 후 greedy 하게 탐색하는 것으로 O(NlogN)에 특정 스테이지 갯수로 가능한지 판별할 수 있다. 이를 이용하면 총 O(N(logN)^2)에 문제를 해결할 수 있다.

여담 : 데이터가 약한 것 같다;;

Silver 2

BOJ 14453 Hoof,Paper,Scissors

문제 설명 : 가위바위보를 하는데, 상대가 낼 순서가 모두 공개되어있다. 나는 계속 똑같은 것을 내다가 중간에 한 번 바꿔서 계속 그것을 내야한다. ex) 가위->가위->가위->가위->바위->바위->바위->바위......... 이때 얻을 수 있는 최대 승수를 구하시오. 

문제 풀이 : 모든 지점에 대해서 시작부터 그 지점까지 H,P,S 중 가장 많이 나온 것의 갯수를 센다. 그 다음지점부터 끝 지점까지 H,P,S중 가장 많이 나온 것의 갯수를 센다. 이 둘의 합이 그 시점에서 변경을 했을때 얻을 수 있는 최대 승수이다. 
각 시점에서 각각 구하지 말고 prefix,suffix를 이용하여 전체를 O(N)에 구하자. 

Silver 3

BOJ 14454 Secret Cow Code

문제 설명 : 기본 문자열에 한 칸씩 밀고 전체를 복사해 붙이는 방식으로 기본 문자열에서 쭉 이어진다. 이때 N번째 문자를 구하시오.

문제 풀이: 한 번 복사가 될때 마다 두 배씩 길이가 증가하므로 현재 위치가 복사하고 붙여넣기전 어느 위치였는지를 계속 판단하여 기본 길이가 될때까지 역추적 하면 된다.

Gold 1

BOJ 14449 Balanced Photo

문제 설명 : 각 소의 키가 주어진다. 어떤 소의 왼쪽에 있으면서 중심 소보다 키가 큰 소의 숫자와, 어떤 소의 오른쪽에 있으면서 중심 소보다 키가 큰 소의 숫자가 2배 이상 차이나는 소의 마릿수를 구하시오.

문제 풀이 : Segment Tree를 이용한다. 가장 키가 큰 소 부터 왼쪽의 소의 수, 오른쪽의 소의 수를 구간 합 쿼리를 이용해 구하고 조건을 만족하는 지 확인한다. 자신의 위치의 인덱스에 1을 업데이트 하는 것으로 이후 소들이 자신보다 큰 소의 수를 셀 때 영향을 준다.

Gold 2

BOJ 14450 Hoof,Paper,Scissors

문제 설명 : Silver2와 같지만 변경할 수 있는 횟수가 추가로 주어진다. 

문제 풀이 : DP로 접근한다. DP[i][j][k]는 i번까지 진행했고, j번 변경을 했으며, 현재 상태는 k인 상태이다. 
dp[i][j][k]=max{dp[i-1][j][k],dp[i-1][j-1][k 이외]}, k가 이길 수 있으면 dp[i][j][k]++을 해주면 된다.

Gold 3

BOJ 14451 안대 낀 스피드러너

문제 설명 : 맵이 주어지고 왼쪽 아래에서 오른쪽 위까지 가야하는데, 맨 처음에 오른쪽, 혹은 위를 보고 있다. 처음에 어느쪽을 보고 있어도 도착할 수 있는 행동의 최소횟수를 구하시오.

문제 풀이 : 정말 다양하게 생각을 해봤는데, 결국은 처음에 위를 보고 있는 경우에 현재 위치와 오른쪽을 보고있을 때의 현재위치를 모두 고려하여 두개의 위치, 돌아간 정도를 5차원 배열로 잡고 dp+bfs를 돌려주면 된다. 구현이 굉장히 짜증난다. 

여담 : 난이도 의견을 보면 다들 이 문제를 풀고 나서 토를 하러 간것을 볼 수 있다. Karuna랑 정말 쓸데 없는 방향으로 많이 고민했다. 제대로 된 풀이를 찾고서도 설마 이거겠어? 라고 하기도 했었다.