백준

이항 계수 3(#11401) Problem 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 (N,K) 를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. Hint 주어진 1000000007은 크기가 큰 소수이다. Solution 큰수의 곱들의 나머지를 구할 때에는 분할 정복을 이용하여 매번 계산시에 나머지를 구한후 나머지로만 남은 연산을 실시하여도 같은 결과가 나온다는 사실은 알고 있어야한다. (나머지 연산 -모듈러 법칙) ps. 사실 법칙 네이밍은 중요하지 않다 수학적 원리를 이해할수 있기만 하면된다. 하지만 마지막에 사용하는 페르마 소정리의 경우에는 과거에 올림피아드 등을 준비하지 않았더라면 일반적인 사람이 미리 알고 있기 쉽지않다. n,k= map(int, inp..

목차 동전 0(#11047) Problem 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. Hint 나머지를 잘 이용해보자 Solution 그리디 알고리즘을 이용한 풀이 n,k=map(int,input().split()) coin=[] cnt=0 for _ in range(n): coin.append(int(input())) for i in coin[::-1]: if i

목차 구간 합 구하기 4(#11659) Problem 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. Solution 누적합을 이용한 풀이 import sys input = sys.stdin.readline n ,m = map(int,input().split()) a = [0]+list(map(int,input().split())) for l in range(2,n+1): a[l]+=a[l-1] res =[] for o in range(m): i ,j = map(int,input().split()) res.append(a[j]-a[i-1]) print(*res,sep='\n') 이 문제는 input이 아닌 readline을 사용하여야지 시간초과를 피할 수 있다. ..

숏코딩보다는 백트래킹, BackTracking 을 이용하여 문제가 원하는 목적에 맞게 풀이해보았다. 목차 N과 M (1)(#15649) Problem 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 Hint 일반적인 백트래킹 방법을 이용하였다. Solution 백트래킹을 이용한 풀이 n, m = map(int, input().split()) res = [] def BackT(depth): if depth == m: for i in res: print(i, end=' ') print() return for i in range(1, n + 1): if i not in res: res.appe..

목차 배수와 약수(#5086) Problem 4 × 3 = 12이다. 이 식을 통해 다음과 같은 사실을 알 수 있다. 3은 12의 약수이고, 12는 3의 배수이다. 4도 12의 약수이고, 12는 4의 배수이다. 두 수가 주어졌을 때, 다음 3가지 중 어떤 관계인지 구하는 프로그램을 작성하시오. 첫 번째 숫자가 두 번째 숫자의 약수이다. 첫 번째 숫자가 두 번째 숫자의 배수이다. 첫 번째 숫자가 두 번째 숫자의 약수와 배수 모두 아니다. Hint 나머지를 이용하여 약수인지 배수인지를 구별하자 Solution 나머지를 이용한 풀이 a=b=1 res=[] while a+b!=0: a,b=map(int,input().split()) if a>b and a%b==0: res.append('multiple') el..

목차 직사각형에서 탈출(#1085) Problem 한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오. Hint 2차원 좌표내 거리 = del x + del y 테두리까지의 거리를 어떻게 표현해야할까 생각해보자 Solution 기하를 이용한 풀이 x,y,w,h=map(int,input().split()) print(min(min(x,w-x),min(y,h-y))) 테두리까지의 최소값은 delx와 y 중에 최소값을 고르면 된다 네 번째 점(#3009) Problem 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째..