오늘은 Atcoder Grand Contest 27에 참가했다. 대회 링크: https://beta.atcoder.jp/contests/agc027A. Candy Distribution Again N명이 원하는 숫자 Ai가 주어진다. 그리고 내가 가진 숫자 X가 있고, 이 X를 N명한테 남김없이 나누어줄 때 정확히 Ai만큼 숫자를 가지게 되는 최대 사람 수를 구하는 문제이다. 정렬한 후 제일 작은 것부터 순서대로 주고 마지막에 남아돌 경우 -1 시켜주면 된다. 간단한 문제. B. Garbage Collector 로봇이 N개의 지점에 주어진 쓰레기를 모두 주워서 버려야 한다. 이 때, 0번째 지점에서 쓰레기를 태우고, 쓰레기를 줍거나 버릴때는 항상 X만큼의 비용을 소모한다. 또, 로봇이 들고 있는 쓰레기의..
16001. 보물상자 열기 문제 링크: https://www.acmicpc.net/problem/16001 카카오 대회 본선 당일에 못 풀었던 문제를 풀었다. 풀이는 비교적 빨리 떠올랐고 결국 그 풀이가 맞았는데, 구현 과정에서 정말 많은 오류를 범했다. 내 풀이는, 1. 맨 왼쪽 위치에서부터 시작해서 오른쪽으로 가면서 팰린드롬 만드는 최소 비용을 찾는다.2. 1번 값을 이용해서 sliding window 같은 방식으로 1,2,3,...번째에서 시작해서 오른쪽으로 가면서 팰린드롬 만드는 최소 비용을 모두 구한다.3. 이렇게 구한 값을 이용해서, 각 시작 위치별로 최소 비용을 찾는다. 이 때 항상 나보다 오른쪽으로 가거나, 왼쪽 끝 지점까지 갔다가 오른쪽으로 가는 비용을 구한다. 이 경우, 2에서 구해둔 ..
BOJ 16122 : Unary 링크 : https://www.acmicpc.net/problem/16122 좀더 식을 깔끔하게 정리했으면 더 간단하게 풀 수 있었을 것 갈은데, 뭐 내가 푼 방법도 조금 느리지만 나쁘진 않은 것 같다. 맨 앞에 한 개를 제외하면 2개의 연산을 묶어서 +1, -1, 그리고 두 종류에 값 변화가 없는 연산 해서 총 4개의 연산자가 있는 것으로 생각할 수 있다. 이러한 연산자를 n개 섞어서 m을 만들면 된다. 이건 적절한 공식들을 섞으면 계산하기 어렵지 않다. 처음에 연산자가 홀수 개인 경우 맨 앞이 -면 그대로, ~면 -x-1로 바뀌므로 이 점을 이용해서 값을 적절히 고친 후 짝수 꼴로 바꿔서 풀면 된다.
오늘은 2018 서울대 프로그래밍 경시대회 오픈 컨테스트에 참가했다. div1을 참가할까 2를 참가할까 하다가 하루종일 머리도 아프고 해서 좀 쉬운 문제나 느긋하게 풀자 생각하고 div2에 참가. 총 8문제를 풀었고, 몸 상태가 안 좋아서인지 코딩 실수를 너무 많이 했다. 대회 끝나고 대회 중에 못 풀었던 한 문제까지 추가로 풀어서 총 9문제. 아래는 푼 문제에 대한 간단한 정리. A. 5차 전직 주어진 n개의 숫자를 정렬한 다음, 맨 처음부터 순서대로 k개씩 더해나가면 되는 문제였다. 간단한 문제. B. 시그널 완전 구현 문제였는데, 그냥 일일히 따서 풀었으면 오히려 패널티가 적었을 텐데 그렇게 하기 싫어서 다른 방법으로 풀다 실수를 많이 해서 여러 번 틀렸다. 이런 문제는 풀 때마다 어떻게 푸는 게 ..
어제 오늘 이틀동안 푼 문제에 대한 정리. 코드포스 201라운드쯤부터 Div2 D~E~F? 를 푸는 연습을 시작했다. 꾸준히 할 수 있을진 모르겠지만 하루에 한 문제라도 푸는 걸 목표로. 아래는 어제~오늘 아침까지 푼 문제들 코멘트. 201D. Lucky Common Subsequence 두 문자열 a,b와 바이러스 문자열 v가 주어졌을 때, v를 substring으로 포함하지 않는 문자열 a,b의 LCS(longest common subsequence)를 구하는 문제다. 세 문자열 길이가 모두 100밖에 되지 않아 단순 DP로 풀기 쉽고, 푸는 과정에서 바이러스 문자열 v를 얼마나 포함하고 있는지를 갱신해주기 위해 KMP 알고리즘의 응용이 필요하다. 문제 자체는 좀 전형적이었는데 KMP 짜는게 잘 기억..