곰탱이의 공부정리

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/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net Pn을 결정짓는 N, 문자열 S의 길이 M, 문자열 S가 주어진다. S에 Pn이 몇개나 들어있는지 알아내는 문제이다 처음 볼 때에는 S를 모두 돌면서 Pn의 개수를 단순히 세면 될 것이라 생각했다. 이 생각을 구현한 코드는 아래와 같다 import sys input = sys.stdin.readline N=int(input().r..

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의 최소공약수만큼이나 처리를 해야해서 시간초과에 걸렸다. 브루트포스를 사용하되 시간을 줄이려면..