궤도

문제 풀이 원의 내접과 외접에 대해 기억이 난다면 이 문제가 그리 어렵지 않을 것이고, 나처럼 기억이 가물가물 하다면 힘들 것이다. 각 좌표(x1, y1 / x2, y2)를 중심으로 하고 반지름이 (r1 / r2)인 원을 그려보자. 류재명이 존재할 수 있는 위치는 각각의 경우에 대해 해당 원의 경계선이다. 원을 2개 그리게 되니까 두 원의 교점의 수가 류재명이 있을 수 있는 좌표의 수다. 그렇다면 두 원의 관계는 어떤 경우가 있을까. 빨간원과 초록원은 조규현과 백승환의 위치가 같은 경우이다. 이 상황에서 두 원의 반지름이 다르면 류재명이 존재할 수 있는 위치는 없고, 같다면 무한하다. 검은원과 보라색원은 두 원의 교점이 1개인 경우다. 각각 내접, 외접하고 있다. 파란원은 교점의 수가 2개이고 주황색 원..

문제 풀이 에라토스테네스의 체를 이용해 소수를 구하는 문제다. 에라토스테네스의 체가 무엇이냐고 물어본다면... 이런식으로 특정 소수의 배수를 전부 지우는 과정을 통해 소수를 구하는 방법이다. 만약 1~n 사이의 소수를 구하고 싶다면 √n 까지만 구하면 된다. 왜일까? n보다 작거나 같은 합성수 m=ab가 있다고 하자. a와 b가 모두 최대일 때는 a=b=√n 일 때이다. a가 이보다 커지면 b가 √n보다 작아지고 반대의 경우엔 a가 √n보다 작아질 것이다. 그러므로 √n 까지만 체크해도 모든 합성수는 지워진다는 것이다. 그렇다면 이제 구현을 할 차례이다. 0과 1은 소수가 아니니 지워주고 2부터 시작한다. 2의 배수를 전부 지워주고, 3의 배수를 전부 지워주고, 4의 배수를 지울 필요는 없다. 왜냐하면 ..

문제 풀이 동적 계획법으로도 풀 수 있을 것 같은데 나는 재귀함수로 풀었다. 입력이 둘 다 1이상으로 들어온다고 하니, 굳이 0층의 사람까지 따질 필요는 없을 것 같다. 0층의 i호에는 i명이 산다고 하니, 1층의 i호에는 1+2+...+i명이 살 것이다. 그보다 높은 층에 대해서도 이 논리는 변하지 않으니 이대로 재귀함수를 짜면 된다. 소스코드 #include using namespace std; int live(int k, int n) { //재귀함수 int people = 0; if (k == 1) { for (int i = 1; i = 1; i--) people += live(k - 1, i); } return people; } int main() { int T, k, n; cin >> T; fo..

문제 풀이 최대한 5kg 봉투를 많이 가져가야 적은 수의 봉투를 가져가게 될 것이다. 그러니 일단 최대한 5kg 봉투에 담는다고 생각한다. 남은 kg수가 0이라면 그대로 루프를 끝내고 3이라면 3kg 봉투 하나 더해주고 끝내면 되지만, 그렇지 않은 경우가 있다. 그렇다면 5kg 봉투를 하나씩 풀면서 3으로 나누어 떨어지는지 확인해 본다. 소스코드 #include using namespace std; int main() { int N, remain, five, three; bool possible = false; cin >> N; five = N / 5; remain = N % 5; if (remain == 0 || remain == 3) { //0 or 3이면 바로 three = remain / 3; p..