곰탱이의 공부정리

https://www.acmicpc.net/problem/15686  치킨거리란 집과 가장 가까운 치킨집 사이의 거리이다. 그리고 도시의 치킨거리란 모든 집의 치킨거리를 합한 것이다. 우리가 주어진 치킨집 중 M개의 치킨집만을 남겨야 할 때, 도시의 치킨거리가 최소가 되게하는 경우의 도시의 치킨거리를 출력하는 문제이다. 이 때 0은 빈곳, 1은 집, 2는 치킨 집으로 인풋이 주어진다.  이 문제는 딱 봐도 복잡한 형식이다. 그렇기에 사실 마땅한 알고리즘보단 하나하나 차분히 나누어 충실히 구현하여 문제를 풀어야한다. 먼저 우리는 집과 치킨집 사이의 치킨거리를 구해서 2d 배열로 저장해놓을 필요가 있다. 그래야 치킨집을 하나씩 없애보며 도시의 치킨거리를 구할 수 있다. 그리고 M개가 될 때까지 치킨집들을 없..

https://www.acmicpc.net/problem/20529 20529번: 가장 가까운 세 사람의 심리적 거리 각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다. www.acmicpc.net 문제가 처음 봤을때는 하나하나 비교하면 못해도 시간복잡도가 O(N^3)이라 시간초과에 걸릴 것이 딱 보였다. 하지만 문제 태그를 보니 비둘기집의 원리가 있는걸 보고 MBTI는 16개 밖에 없으니 사람이 33명 이상이라면 못해도 3명은 같은 MBTI라 심리적 거리가 0이 되는 경우가 있다는 걸 알게 되었다. 그러므로 N이 32 이하 일때만 무식하게 브루트포스로 구하고 그 33 이상이라면 그냥 0을 출력하게 만들었다. import sys input = sys.stdin.readline T=int..

https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net M,N이 주어지고 x,y가 주어진다. 현재 년에 대한 표시는 로 한다. 예시를 풀어보자면 현재 년을 M,N으로 나눈 나머지가 각각 x,y이다. 가장 처음한 생각은 그냥 브루트포스로 1부터 최대년까지 다 M,N으로 각각 나눈 나머지가 x,y일 때를 답으로 출력하는 것이었다. 하지만 이러한 방법으로 하니 M과 N의 최소공약수만큼이나 처리를 해야해서 시간초과에 걸렸다. 브루트포스를 사용하되 시간을 줄이려면..