1.풀이 합이나 평균을 구할때 수학적 사고를 하자! ​ (1) i번째 숫자가 (0~9중)될 수 있는 모든 수를 찾는다. ex) digitLSize=[[1],[0,8],[8,9]] => 100의자리에 1이 올 수 있고, 10의자리는 0,8이 올 수 있고, 1의자리는 8,9가 올 수 있다. ​ (2) 될 수 있는 모든 경우의 수를 찾는다. * dfs로 완전탐색하려 했지만 메모리 초과가 났다(소스코드1) * 각자리에 올 수 있는 숫자를 나올수 있는 횟수만큼 더하면 총 합을 구할 수 있다. (소스코드2) 위의 예시에서 100의 자리 1은 총 2*2번나오므로 100*1*4, 10의자리 0은 총 1*2번나으모르 10*0*2... ​ 2. 소스코드 (1) 소스코드1 (메모리초과) import sys sys.setre..

파스칼의 삼각형으로 조합을 구할 수 있다. 위의 삼각형 형태를 행렬로 바꾸면 하삼각행렬로 만들 수 있다. (i,j)위치의 값이 정확히 iCj가 되는 예쁜 형태가 된다. (j==0일때만 1을 넣어주면된다.) ​ ex)[boj]11051_이항계수2 #include #include using namespace std; long long pascal[1000][1000]; int main() { int N, K; int max = 10007; cin >> N >> K; for (int n = 0; n

1.풀이 (1) a의 b승을 구하는문제. 진짜 a를 b번 곱하면 당연히 시간초과. (2) a^b => (a제곱)^(b//2) 로 계산하는것이 핵심. EX) 2^4는 2를 네번곱해야 하지만, 2^4->4^2->16^1로 하면 3번만에 계산가능 (3) 제곱수가 홀수인 경우는 하나빼서 계산해야 하기 때문에 경우의 수를 나눠준다. (4) 제곱수가 1이 될 때 까지 재귀를 반복한다. ​ 2. 소스코드 A, B, C = map(int, input().split()) def power(a,b): #1이면 끝 if b==1: return a%C #짝수이면 제곱 if b%2==0: return power(a**2%C,b//2) #홀수이면 곱하고 제곱 else: return (a*power(a**2%C,b//2))%C d..

1. 풀이 처음엔 N개의 점을 모두 사용하여 N/2개의 선분을 만들었을 때 선분의 합이 최소가 되는 경우를 구해야 한다고 생각했다. 따라서 nC2*n-2C2*n-4C2...*4C2*2C2의 경우를 생각했었다. 하지만 문제에서 요구하는것은 "벡터의합의 길이"이다. ​ 즉 4개의 점 (x1,y1),(x2,y2),(x3,y3),(x4,y4) 가 있을 때 (x_a+x_b -x_c-x_d , y_a+y_b-y_c-y_d )의 길이의 최솟값을 구하면 된다. ​ 따라서 모든점의 개수(N개)중 시작점의 개수(N//2)를 뽑는 경우(나머지는 자동으로 도착점이 된다)는 nCn//2 이므로 해당 경우를 완전탐색하면 답이 된다. ​ 2.소스코드 import sys from itertools import combinations..

0~size-1까지의 모든 숫자들에 대해서 소수인지를 판별 1. isNotPrime는 소수인것이 0 int isNotPrime[size]; void eratosthenes(size) { isNotPrime[1] = 0; isNotPrime[1] = 1; // 0과 1은 소수가 아니다. for (int i = 2; i*i < size; i++) { if (!isNotPrime[i]) { //소수이거나, 아직 탐색을 안했다면 (isNotprime은) 0 for (int j = i * i; j < size; j += i) { isNotPrime[j] = 1; } } } } 2. isPrime는 소수인것이 1 #에라토스테네스 isPrime=[1 for i in range(size)] def prime(): is..

1. a와 b의 최대공약수를 찾는것 2. a%b가 0이면 a가 최대공약수 3. 그렇지 않으면 (b,a%b) 형태로 만들어서 다시 계산 4. 첫번째 반복에서 a

1. 두 수(A와 B) 의 약수들을 각각 모두 비교해준다 2. 비교 => A의 약수 a_n, B의 약수 b_n의 최대공약수를 뽑아서 최종답 ans에 곱해준다. 3. 숫자 = 숫자 % 10^9 + 10^9 해주면 숫자가 커지지 않고, 뒤에 9자리는 계속해서 보존 ​ ex) [boj]2824_최대공약수 #include #include #include using namespace std; int arrA[1001]; int arrB[1001]; int euclid(int a, int b) { int temp; while (1) { if (b == 0) { return a; } else { temp = b; b = a % b; a = temp; } } } int main() { int N, M; long lon..

소수구하기 수행시간(1,679 ms) 수행시간(6,004 ms이상) L=[2] for i in range(3,1000001,2): isDecimal=True for j in L: if i%j==0: isDecimal=False break if isDecimal==True: L.append(i) print(*L) 소수가 아닌수 a는 a보다 작은 소수에 의해 나누어 떨어짐 def isDecimal1(a): import math if a==2: return True if a==1 or a%2==0: return False for i in range(3,int(math.sqrt(a))+1,2): if a%i==0: return False return True L=[] for i in range(1000000):..

1. 풀이 (1) 늦게 끝낼 수 있는 일부터 탐색하여 최대한 늦게 시작한다. (2) (1)에서 탐색한 일이 이전의 일의 데드라인에 영향을 주면, 이전의 일을 영향받는만큼 늦게 시작한다. 2. 소스코드 N=int(input()) L=[] for i in range(N): L.append(list(map(int,input().split()))) def returnSecond(L): return L[1] L.sort(key=returnSecond) preStart=L[N-1][1]-L[N-1][0] for i in range(N-2,-1,-1): if preStart

1. 풀이 모든 문제는 푸는데 1시간이 걸리기 때문에, 컵라면을 가장 많이주는걸 그리디하게 고르면 된다. 이때 문제마다 데드라인이 다르기 때문에 시간을 뒤에서부터 1시간 단위로 탐색하면서 먼저 끝나는 일 중에 컵라면을 많이 주는 것부터 차례대로 수행하면 된다. 2. 소스코드 from collections import deque import heapq N=int(input()) L=[] for i in range(N): L.append(list(map(int,input().split()))) # t시간까지 해야되는거 pq에추가 def addPQ(t): while(L): dead,cup=L.pop() if dead==t: heapq.heappush(cupPQ,-1*cup) else: L.append([dea..

1. 풀이 (1) 주유소의 위치를 기준으로 가까운 순으로 정렬을 한다. (2) 현재위치에서 최대로 갈 수 있는 위치를 확인한다 - 갈 수 있는 위치가 도착지점을 넘으면 -> 종료 - 넘지 않으면 -> 갈 수 있는 위치까지의 주유소 중 가장 주유를 많이 할 수 있는 곳에서 주유 (3) 주유한 만큼 위치이동 (4) (2),(3)을 반복 2. 소스코드 import heapq import sys from collections import deque N=int(input()) point=[] for i in range(N): a,b=map(int,sys.stdin.readline().rstrip().split()) point.append([a,b]) L,P=map(int,input().split()) point...

Q. 각각의 시계추의 무게가 주어질 때 ( ex) weight=[3, 1, 6, 2, 7, 30, 1] ) 시계추로 잴 수 없는 가장 작은 양의 정수는? 1. 풀이 오름차순으로 정렬된 weight를 앞에서 누적하여 더해가며, 다음으로 큰 숫자보다 그 합이 작을때 stop => 더이상 더할것이 없으므로 2. 소스코드 def solution(weight): weight.sort() length=len(weight) s=1 for i in range(length): if s

1. 풀이 (1) 현재 가지고 있는 기름으로 방문가능한 모든 주유소 중에 가장 기름을 많이 넣을 수 있는 주유소를 후보에 추가한다. (이때 후보주유소는 힙으로 관리한다. 게속 추가하고 매회 최댓값을 추출해야 하기 때문) (2) 후보(heap)에서 최댓값을 추출한다. (이때 방문횟수를 +1) * 만약 방문할 주유소가 없으면 답은 -1 2. 소스코드 import heapq import sys from collections import deque N=int(input()) point=[] for i in range(N): a,b=map(int,sys.stdin.readline().rstrip().split()) point.append([a,b]) L,P=map(int,input().split()) point...