문제 링크: https://www.acmicpc.net/problem/8098 문제 요약n개의 구간이 있다. 각 구간은 (p,k)로 구성되며 각 숫자는 1이상 30000이하이다. 서로 다른 두 구간은 겹치게 선택할 수 없을 때, 선택한 구간들의 전체 길이 합의 최댓값을 구하여라(단, 두 구간에 대해 한 구간의 끝점과 다른 구간의 시작점이 같은 경우는 선택할 수 있다). 풀이일단 하나의 구간만 놓고 생각해보자. 특정한 한 구간을 골랐을 때, 이 구간을 맨 끝 구간으로 포함하는 길이 합의 최댓값은 어떻게 구할 수 있을까? 간단하게 생각하면, 현재 구간이 (l,r)일 때 1~l까지의 최댓값 + 현재 구간의 길이가 곧 전체 최댓값이 될 것이다. 이러한 논리를 반복적으로 적용하면, dp(pos) = 1 ~ pos..
문제 링크: https://www.acmicpc.net/problem/8094 문제 요약w와 5이상 w이하의 숫자 n개가 주어진다. 이 숫자들을 몇 개의 그룹으로 묶을 건데, 각 그룹에는 최대 2개의 숫자가 들어갈 수 있고 그 두 수의 합은 w를 넘으면 안 된다. 또, 모든 숫자가 그룹에 포함되어야 한다. 이 때 가능한 한 최소 그룹 개수를 구하여라. 풀이그리디한 접근 방법으로 풀 수 있다. 직관적으로, 제일 작은 숫자부터 숫자 k에 대해서 w-k이하인 숫자들 중에 제일 큰 걸 그 k와 묶어주면 답이 될 것이다 라는 생각을 할 수 있고(그렇게 해야 최대한 해당 한 그룹에 많이 넣을 수 있으니까), 그 생각대로 구현하면 AC를 받을 수 있다. 이런 그리디한 문제는 답 보다도 그 풀이의 정당성에 대한 증명이..
문제 링크: https://www.acmicpc.net/problem/8103 문제 요약n x n 크기의 체스판 위에 n개의 룩을 서로가 서로를 잡을 수 없게 배치할 것이다. 이 때, i번째 룩은 (ai,bi) 에서 (ci,di)위치 사이에만 놓을 수 있다. 모두 배치할 수 있다면 그렇게 배치할 수 있는 경우를 아무 것이나 출력하고, 배치할 수 없다면 NIE를 출력하라. 풀이 록끼리 서로가 서로를 잡을 수 없게 배치하려면, 하나의 룩이 배치된 위치와 같은 행 또는 열에는 다른 룩이 배치되어선 안 된다. 또, 룩은 항상 일직선으로만 위치를 차지하기 때문에 행과 열은 독립적이다. 따라서, 행과 열을 분리해서 보아도 상관없다. 룩이 x좌표에서 어느 위치에 있느냐는 그 룩의 y 좌표에서의 배치에는 전혀 영향을 ..
* 이 글은 해당 대회 문제의 풀이에 대한 스포일러를 포함하고 있습니다. 2회 대회도 개최한지 몇 달은 넘게 지났는데 이제서야 후기를 쓰는게 좀 우습기도 하지만, 대회 개최 하면서 느꼈던 점에 대한 걸 좀 정리해두고 싶어서 그냥 1,2회 다 글을 쓰려고 한다. 소프트콘은 뭔가 마음 편하게 참여할 수 있으면서 문제가 재밌는 그런 대회를 꾸준히 열고 싶은 생각에 개최를 하게 됐다. 이 대회는 내가 직접 개최하는 만큼 철저하게 내 취향에 맞는 문제로 구성하고 싶었다. 내 문제 취향은 꽤 명확한데 요약하자면 다음과 같다. 1. 수학적인 문제보다는 컴퓨터적인 구조나 사고방식을 요하는 문제2. 어려운 알고리즘, 자료구조에 대한 사전 지식이 필요 없는 문제3. 그 문제만이 갖고 있는 고유한 성질에 대한 관찰이 많이 ..
오늘은 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 짜는게 잘 기억..