문제 링크: 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. 그 문제만이 갖고 있는 고유한 성질에 대한 관찰이 많이 ..