Doby's Lab

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 이번 문제는 (https://jaimemin.tistory.com/682)을 참고한다. 개념 학생 때 배웠던 nCr 개념이 등장한다. 정확히는 n Combination r이라고 부른다. 이와 같이 따라오는 게 nPr로 이는 n Permutation r이라고 부른다. 이 둘은 조합론으로 둘 다 공식이 존재한다. 솔루션 1 (실패) 이 공식을 활용하여 두 개의 팩토리얼 함수를 구현하여 풀려고 했다. [조금 다른 방식의 팩토리얼 함수] 각각 n!, (n - r)!, r! 은 시간이 오래 걸릴뿐더러 숫자까지 너무 커질 ..

https://www.acmicpc.net/problem/11561 11561번: 징검다리 각 테스트 케이스마다 한 줄에 승택이가 밟을 수 있는 최대 징검다리 수를 출력한다. www.acmicpc.net 이번 문제는 수학 카테고리에 넣고 싶었으나 그래도 문제의 베이스는 이분 탐색이라서 이 카테고리에 넣어둔다. 점프를 최대로 하려면 1칸 점프를 한 뒤, +1 점프, +1 점프로 목적지에 도달해야 최댓값이 도출될 수 있다. 하지만, 100칸이 있을 때는 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14까지 더하면 100이 넘는다. 그래서 이럴 경우에는 13번째 점프를 할 때, 100을 채우게끔 22칸을 뛰어주면 된다. 즉, 코드로 구현을 할 때는 val..

이번 문제 논리는 굉장히 어려울 줄 알았다. 어떻게든 솔루션을 발견하려고 각 값의 연관성을 찾으려 했다. 그 결과 TC에서 논리를 찾을 수 있었다. Input 10 12 3 9 Output 33 10과 12 즉, M과 N의 차이는 +2다. x와 y의 차는 +6이다. 이를 보고, +6은 +2의 3배니까 3바퀴 정도 돌면 차이가 3배만큼 벌어질 거 같다는 생각에 10을 기준으로 3바퀴를 돌려보니 30과 30 각각의 M과 N으로 나눈 나머지는 0과 6이 나온다. (정확히 말하면 10은 3바퀴, 12는 2바퀴 돌고 6번의 해가 지난 것이다.) 여기서 3번의 해가 더 지나면 3 9가 x, y값과 일치하면서 맞아떨어진다. (10을 기준으로 3바퀴 돌렸으므로) 10 * 3 + (3번의 해가 지났으므로) 3 = 33 ..