한 걸음씩 기록하며

⛏ 문제 파악 줄 서있는 사람 숫자와 해당 사람들의 인출 시간을 주고, 최소 시간을 구하는 문제 앞의 시간을 계속 더해야하니, 가장 시간이 적게 걸리는 사람을 앞에 배치하는 것이 최소값을 구하는 키 👉🏻 답안 from sys import stdin N = int(input()) waiting = list(map(int, stdin.readline().split())) waiting.sort() min = 0 for i in range(N): for j in range(0, i+1): min += waiting[j] print(min) 📑 간단한 설명 최소 시간을 구하기 위해, waiting을 오름차순으로 변경 이중 for문을 통해서, 각 기다리는 시간을 더하여 값을 구했다.

⛏ 문제 파악 N 종류의 동전이 주어지고, K라는 값이 주어짐 주어진 동전의 종류의 최소한의 갯수로 K라는 값을 만드는 문제 👉🏻 답안 - 패스한 답안 N, K = map(int, input().split()) need = 0 coins = [] for _ in range(N): coin_type = int(input()) coins.append(coin_type) coins.reverse() for coin in coins: if K == 0: break need += K // coin K %= coin print(need) - 시간 초과 뜬 답안 N, K = map(int, input().split()) need = 0 coins = [] for _ in range(N): coin_type = in..

⛏ 문제 파악 괄호를 적절히 쳐서 주어진 식의 값을 최소로 만드는 문제 최소로 만드려면, -를 기준으로 안에 있는 값들을 괄호로 묶으면 된다. 가령 55-50+40-30+40 이라는 식이 주어졌다면, 아래와 같이 -를 기준으로 괄호로 묶으면 최소값이 된다. 55 - (50 + 40) - (30 + 40) 👉🏻 답안 from sys import stdin line = list(stdin.readline().strip().split('-')) sum = 0 for i in line[0].split('+'): sum += int(i) for i in range(1, len(line)): x = line[i].split('+') for j in range(0,len(x)): sum -= int(x[j]) pr..

⛏ 문제 파악 이항계수(Binomial Coefficient) 이항계수는 조합론에서 등장하는 개념으로 주어진 크기 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 가짓수를 일컫는다. 2를 상징하는 ‘이항’이라는 말이 붙은 이유는 하나의 아이템에 대해서는 ‘뽑거나, 안 뽑거나’ 두 가지의 선택만이 있기 때문이다. 이항계수를 찾아보니.. 이항계수의 성질을 이용하여 동적 계획법?을 만드는 알고리즘도 있던데 너무 어려워서 그건 포기했다.. 그냥 여기에서는 조합론의 기본인 팩토리얼로 이항계수 구하는 법 정도만 하겠다.. 👉🏻 답안 N, K = map(int, input().split(' ')) def factorial(n): # 팩토리얼 구하는 함수 ans = 1 for i in range(2, n+1): ans..

⛏ 문제 파악 최소공배수를 구하는 문제로, 바로 좀 전에 푸는 문제와 사실 중복이다. 유클리드 호제법으로 풀면 된다. 물론 파이썬 math도 가능 👉🏻 답안 T = int(input()) def gcd(a, b): while b != 0: r = a % b a = b b = r return a def lcm(a, b): lcm = (a * b) // gcd(a, b) return lcm for i in range(T): X, Y = map(int, input().split()) print(lcm(X,Y)) import math T = int(input()) for i in range(T): X, Y = map(int, input().split()) print(math.lcm(X, Y)) 📑 간단한 설..

⛏ 문제 파악 말 그대로 최대공약수와 최대공배수를 구하는 문제 최대공약수(GCD / Greatest Common Divisor) : 두 수의 공통된 약수인 정수로, 약수 중에 제일 큰 수 최소공배수(LCM / Least Common Multiple) : 양의 공배수 가운데 가장 작은 수 유클리드 호제법으로 문제를 풀면 된다. 유클리드 호제법 유클리드 호제법은 2개의 자연수 또는 정수의 최대공약수를 구하는 알고리즘의 하나로, 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정수) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수(gcd)는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r..

⛏ 문제 파악 약수를 구하는 문제 진짜 약수는 서로 곱했을 때 원래의 수가 출력되는 숫자 약수 중 최소값이랑 최대값을 곱하면 원래 값이 출력되므로, 이 방식으로 풀면 된다. 👉🏻 답안 N = int(input()) X = list(map(int, input().split(' '))) print(max(X) * min(X)) 📑 간단한 설명 max, min 함수로 최소값, 최대값 곱하면 된다.

[크레인 인형뽑기 게임] 👉🏻 답안 def solution(boards, moves): answer = 0 bucket = [] // 뽑은 인형을 두는 스택 for move in moves: for board in boards: if board[move-1] != 0: // 0이 아니면 인형이 있으니 뽑아서 bucket.append(board[move-1]) // 바구니에 넣어라 board[move-1] = 0 // 그리그 그 인형 칸을 0으로 만들어라 break if len(bucket) >= 2 and bucket[-1] == bucket[-2]: // 바구니에 후입된 2개의 인형이 같으면 answer += 2 // 카운트하고 bucket = bucket[:-2] // 2개를 파괴! return an..