돌이 코딩하는 방

BUSACO 2017 February Contest에 대한 전체 풀이를 작성하려고 한다. Bronze ~Gold 까지는 전부 작성하고 Platinum은 되는대로 추가할 예정이다. 소가 길을 건너는 이유 시리즈 이고, 한글 번역이 되어있으므로 따로 문제 설명은 하지 않으려 한다. 백준에서는 https://www.acmicpc.net/category/396 에서 볼 수 있다. Bronze 1 문제 설명 : https://www.acmicpc.net/problem/14467 문제 풀이 : 배열에 최근 위치를 저장해서 현재 받은 입력이 최근 위치와 달랐는지 판별하고 횟수를 세준다. 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include using namespace..

USACO 2017 January Contest에 대한 전체 풀이를 작성하려고 한다. Bronze ~Gold 까지는 전부 작성하고 Platinum은 되는대로 추가할 예정이다. 백준에서는 https://www.acmicpc.net/category/395에서 볼 수 있다. Bronze 1 BOJ 14455 Don't Be Last 문제 설명: 우유를 얻은 소와 양이 여러차례에 걸쳐 주어질 때 마지막에서 두번째로 적은 양의 우유를 얻은 소를 구하시오. 문제 풀이: 구조체등을 이용하여 이름과 우유의 양을 같이 저장하자. 이름에 맞춰 짠 우유의 양을 더해주고, 정렬을 해서 출력하면 된다. 여담: 다른 브론즈 문제보다 오히려 어려웠다. 구현과정에서 고려해야 할 것이 적지 않고 은근히 까다로운 문제. Bronze 2..

USACO 2018 February Gold 3번이다. BOJ 15747번에 등록되어 있으며 문제는 여기서 볼 수 있다. 문제 설명 문제해석과 이해가 굉장히 어려운 문제다. N이 주어지고 우리는 총 N개를 k개의 그룹으로 나눠야 한다. 이때 나눈 그룹별로 숫자가 0부터 1씩 올라가며 부여된다. 예를 들어 9를 4 3 2로 분할 했다면, (0,1,2,3)(0,1,2)(0,1)이 된다. 이때 분할 후에 매겨진 값으로 만들어진 배열이 주어진 배열과 최소 몇 개가 다른지 n 이하의 모든 k에 대해서 출력해야 한다. 예제를 예시로 들자면 1개의 그룹은 무조건 0,1,2,3,4,5로 1,2 만 같습니다. 2개의 그룹으로 나눌 때는 0,1,2,3 0,1 로 나누어야 다른 원소가 2개로 가장 적습니다. 3개의 그룹으로..

USACO 2018 US Open Gold 2번이다. BOJ 15758번에 등록되어 있으며 문제는 여기서 볼 수 있다. 문제 설명 첫 줄에 n과 m이 주어진다. n는 소의 숫자이며, m은 세트의 숫자이다. 다음 m개의 줄에 한 세트씩 입력이 들어온다. 한개의 세트에 대한 입력은 k와 k개의 숫자로 구성된다. k개의 숫자는 소들의 순서관계이다. 우리는 위에서부터 최대한 많이 순서를 지켜서 소들을 정렬 시키려고 한다. 순서가 상관없는 소들에 대해서는 숫자가 작은 소를 우선으로 정렬한다. 이때 위에서 부터 지킬 수 있는 조건의 갯수와 그 정렬방법을 출력해야 한다. 문제 풀이 문제를 보자 마자 바로 떠오르는 개념이 있다. "위상정렬". 위에서 부터 최대 몇 개까지의 조건을 지킬 수 있는지를 알 수 있다면 Pri..

USACO February 2016 Contest Gold 2번이다. BOJ 11994번에 등록되어 있으며 문제는 여기서 볼 수 있다. 문제 설명 영어 디스크립션을 읽기 싫을 수도 있으니 대충 문제 설명을 하려고 한다. 첫째줄에 N과 K가 주어진다. N은 총 방의 갯수로 방은 중앙 정원을 기준으로 원형으로 둘러져 있다. 시계처럼 생각하면 된다. 소들은 모두 중앙에 있고, 우리는 그 중 잘 K개의 방문을 연다. 그 다음에는 N개의 숫자가 주어진다. 이는 최종적으로 1부터 N번방에 들어가야하는 소의 수이다. 소들은 열려진 방으로 들어가서 시계방향으로만 이동할 수 있다. 이때 소들의 이동거리의 합의 최솟값을 구하는 것이다. 예제 설명 위 링크의 예제에서 2번방돠 5번방을 열면 2,3,4번방에 가야하는 소들은 ..

USACO 풀이글들을 본격적으로 적기 전에, 이런저런 이야기를 적어보려고 한다. USACO는 나와 굉장히 관련이 깊다. 옛날에 한창 늅늅이고 잘해지고 싶던 마음이 강했던 시절, 정올 국대님 몇 분 한테 무슨 문제를 풀면 좋을지를 물어보았었다. :GOD:들의 답은 한결같았다. USACO를 돌아라. 멀리 메일을 보냈더니 근처 사람이 대답해준 사건도 있었지만, 아무튼 USACO는 좋은 셋이다라고 많이 이야기한다. 문제의 질 자체도 괜찮을 뿐만이 아니라 풀이도 다 제공이 되기 때문이다. 그래서 나는 USACO를 많이 돌았다. silver를 쭉 돌고, 공부 좀 하다가 다시 gold를 돌았다. 셋을 도는 것의 장점은 지금까지 내가 배운 내용들 중 문제에 맞는 적합한 알고리즘을 선택하는 과정부터 시작할 수 있다는 것..