Redddy's Devlog

📖 Solution 문제의 요구사항을 정리해보면 길이 n의 조합중에서 x배수의 숫자의 합에서 y배수의 숫자의 합의 차를 가장 크게 만들 수 있는 조합을 찾고 그 차를 출력하는 문제이다. A - B의 차를 크게 만들기 위해서는 A를 최대한 크게, B를 최대한 작게 만들면 된다. 그렇다면 x의 배수 위치에는 n부터 내림차순으로 배치하고, y의 배수 위치에는 1부터 오름차순으로 배치하면 된다. 둘이 겹치는 부분이 있을 수 있는데 이는 0이 되기 때문에 상관없다. 그렇다면 이제 구해야 하는 점은 n에서 x 배수의 갯수, y 배수의 갯수 그리고 겹치는 부분이다. 이 겹치는 부분은 lcm 을 사용하여 찾을 수 있다. 💻 Code HTML 삽입 미리보기할 수 없는 소스 🔗 Problem https://codeforc..

📕 풀이 A와 B와 C가 공백을 두고 입력된다. 우리는 (A^B)%C 값을 출력하면 된다. 단 A,B,C 는 모두 2,147,483,647 이하의 자연수이다. 수의 범위가 방대하다. 때문에 21억번 곱한다면 O(N)이여도 시간초과가 날 것이다. 그래서 나머지 분배법칙과 지수법칙을 사용하여 답을 구하였다. 📖 지수법칙 (A^m)^n = (A^(m * n)) 📖 나머지 분배 법칙 (AxB) % C = (A%C) * (B%C) % C 우선 지수 법칙을 사용하여 분할 정복을 한다. 2 ^ 32 의 값을 계산하는 방법은 2를 32번 곱하는 방법도 있지만 지수법칙을 사용하여 (2^16)^2 16번 곱한 것을 제곱하는 방식으로 하면 총 17번의 연산으로 줄일 수 있다. 이 방법을 계속 사용하면 10번, 연산 7번만에..

🔗 문제링크 : 분수찾기 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 📕 문제 풀이 문제 풀이 하기전에 조금 주저리 주저리 하자면,,, 요즘 조금 바빠서 글 올리는 빈도수가 조금 줄었다. 그래도 하루에 하나씩은 올리려고 노력하고 있움!!! 파스칼의 삼각형(?) 과 비슷한 방향으로 움직이는데 한번은 오른쪽으로, 한번은 왼쪽으로 이런식으로 반복한다. 그리고 분수의 숫자들은 분자 + 분모 값이 하나씩 증가한다. 이 점을 이용하여 코드를 짰다. 💻 코드 div = [i for i in range(1, 4473)] n = int(input()) cnt = 1 for d in div: if n - d

🧩문제 해석 자리수 n이 주어졌을 때 그 n 자리수인 신기한 소수를 출력하는 문제 신기한 소수란 n = 4 일 경우 num[0] 도 소수 num[:2] 도 소수 num[:3] 도 소수 num 도 소수라면 num은 신기한 소수이다. 즉 첫번째 숫자도, 첫번째부터 두번째숫자도, ... 첫번째부터 n번째숫자도 소수라면 신기한 소수인 것이다. 🔍 고민 모든 숫자를 대입해가며 소수인지 판별한다면 시간초과가 날게 뻔했다. (요즘 시간초과가 많이 난다...ㅎ) 예제 문제를 보니 알 수 있는 점이 있었다. 첫번째 숫자는 무조건 2,3,5,7 이고 그 다음에 오는 숫자들은 1,3,7,9 들이 막 조합되어서 나타났다. 돌려볼 숫자들이 절반이상 줄어들었다! 첫번째 숫자가 2, 3, 5, 7 인 이유! 어찌보면 당연한 이야기..

📎문제링크: https://www.acmicpc.net/problem/1673 1673번: 치킨 쿠폰 강민이는 치킨 한 마리를 주문할 수 있는 치킨 쿠폰을 n장 가지고 있다. 이 치킨집에서는 치킨을 한 마리 주문할 때마다 도장을 하나씩 찍어 주는데, 도장을 k개 모으면 치킨 쿠폰 한 장으로 교환 www.acmicpc.net 💼서론 취킨먹고싶다🍗 🧩문제 해석 치킨을 주문하는데에는 쿠폰이 필요하다. 그리고 치킨 한마리 시킬때마다 도장을 하나찍어주는데 k개의 도장을 찍으면 한개의 쿠폰과 교환할 수 있다. 또 이렇게 구매한 치킨에도 도장을 찍어준다! 또한 문제의 테스트케이스가 주어지지 않기 떄문에 무한 루프를 돌리고 시스템 종료 처리도 잘 해줘야한다. 📘풀이 1. 우선 가지고 있는 쿠폰 n개와 쿠폰 n개로 구매..

처음에는 단순히 itertoors에서 combinations를 import해서 사용했는데 예상했던대로 시간초과가 나왔다. (요즘 문제 푸는데 시간초과가 너무 많이 나와...ㅜ) 그래서! 조합을 combinations를 사용하는 것이 아니라 식을 factorial을 불러와서 조합의 경우의 수를 만들어 주었다. 📚 풀이 1. math 모듈을 가져와 factorial을 사용한다. 2. mCn 을 factorial을 사용해서 만든다면 => (m!/(m-n)!)/n! 3. 2번에서 사용한 식을 컴퓨터에서 실행하면 오차가 발생한다. (23 24 입력시 23.9999996이 나옴) 그래서 어차피 몫과 값이 다를리가 없기 때문에 /가 아닌 //를 사용해준다. 💻 코드 import sys, math input = sys..