문제https://www.acmicpc.net/problem/13241 풀이두 수 a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수로 나눈 것과 같다.LCM(a, b) = (a * b) / GCD(a, b)이때 a와 b의 최대공약수를 구하는 함수는 유클리드 호제법을 사용하여 구현하였다. 유클리드 호제법 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란ko.wikipedia.orgA, B = map(int, input().split())def GCD(a, b) : if a
문제https://www.acmicpc.net/problem/14246 풀이투 포인터를 적용해서 풀었다.left와 right 모두 0에서 시작해 특정 조건을 만족하면 인덱스를 하나씩 늘려갔다.이때 주어진 값들은 모두 자연수이므로, 만약 left ~ right의 구간합이 k보다 크다면 right 이후의 모든 구간 또한 k보다 큰 구간합을 갖는다.ex. [1 2 3 1] 에서 4 이상의 구간합을 찾는 경우, [1 2 3]의 합이 4보다 크므로 [1 2 3 1]의 구간합 또한 4보다 크게 된다.n = int(input())nums = list(map(int, input().split()))k = int(input())left, right = 0, 0sum = 0count = 0while (lef..
문제https://www.acmicpc.net/problem/1182 풀이주어진 숫자 집합 S 중에서 순서에 관계없이 숫자 6개를 뽑는 문제이다.백트래킹으로 해결했다.def choose_num(start) : if len(selected_idx) == 6 : # 6개 숫자를 모두 뽑았으면 결과 출력 for idx in selected_idx : print(S[idx], end = ' ') print() for i in range(start, k) : # 순서 상관없이 겹치지 않게 뽑아야 하므로 start 지정 selected_idx.append(i) choose_num(i + 1) selected_idx.pop()while True : k, *S = m..
문제https://www.acmicpc.net/problem/13305 풀이첫 번째 시도앞으로 남은 도시들과 비교했을 때 현재 도시의 가격이 가장 저렴하면 남은 거리를 갈 수 있을만큼 최대로 채우고, 그게 아니라면 다음 도시까지 이동할 만큼만 채우자.ex. 도시의 주유소 가격 : 5 2 4 1첫 번째 도시(가격 5) : 다음 도시로 이동할 만큼만 채우기두 번째 도시(가격 2) : 남은 도시(마지막 도시 제외) 중 가장 저렴한 가격이므로, 마지막 도시까지 갈 수 있을만큼 채우기더보기import sysinput = sys.stdin.readlineN = int(input())length = list(map(int, input().split()))price = list(map(int, input().sp..
문제https://www.acmicpc.net/problem/2583 풀이dfs를 사용해 풀이했다.import syssys.setrecursionlimit(10**6)M, N, K = map(int, input().split())maps = [[0 for _ in range(N)] for _ in range(M)]# 직사각형이 그려진 부분을 -1로 표시한다.for _ in range(K) : x1, y1, x2, y2 = map(int, input().split()) for i in range(x1, x2) : for j in range(y1, y2) : maps[j][i] = -1# 한 영역의 넓이를 구하기 위한 dfs 함수def dfs(x, y) : global count # 한..
문제https://www.acmicpc.net/problem/10610 풀이우선 주어진 숫자들의 조합으로 30의 배수를 만들 수 있는지를 판단해야 한다. 배수 판정법 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 배수 판정법은 배수인지 확인하려는 수의 배수가 맞는지 간단히 확인하는 절차이다. 일반적으로 정수 m , n {\displaystyle m,n} 에 대해 m {\displaystyle m} 이 n {\displaystyko.wikipedia.org30의 배수는 3의 배수이면서 일의 자리가 0인 수이고, 3의 배수는 각 자리 수의 합이 3의 배수인 수이므로주어진 숫자에 '0'이 포함되고, 각 자리 수의 합이 3의 배수가 된다면 주어진 숫자들의 조합으로 30의 배수를 만들 수 있..
