본문 바로가기

알고리즘/SWEA19

SWEA D3 17642. 최대 조작 횟수 (python) 최대 조작 횟수 풀이 문제를 보고 이 뭔 말이고... 하고 있었다. 그러다가 보다보니 최대한 많은 횟수로 조작해야 하고 소수를 사용해야 한다고 하는데, 대신 1이 아닌 수로 조작을 해야 된다고 한다. 우선 난 함수를 만들어서 풀이를 했다. 1. A>B 또는 B-A == 1이면 조작으로 해결이 불가능하므로 -1을 반환 2. A==B이면 조작할 필요가 없으니 0을 반환 3. 이외의 경우에는 홀수와 짝수일 때를 구분해서 짝수면 차이의 //2를 해주면 된다. 홀수도 마찬가지로 //2를 해주면 되는데 이유는 +2만 하다가 중간에(마지막이든 처음이든) +3만 한 번 해주면 해결되기 때문이다. 3-1. 그런 이유로 홀수든 짝수든 상관없이 (B-A) // 2의 값을 반환해 주면 된다. def solution(A,B):.. 2024. 2. 25.
SWEA D3 16800. 구구단 걷기 (python) 구구단 걷기 풀이 무한한 A*B 행렬(인덱스가 1부터 시작하는)의 칸이 있다고 할 때, 각 칸은 각 인덱스를 곱한 숫자가 들어간다. 예시에서도 말했듯이 9*9라면 구구단값이 들어있다. 이런 행렬이 있다고 가정하고, 주어지는 N의 값이 있는 칸으로 이동하려고 할 때, 가장 적은 이동을 할 수 있다면 몇 칸을 이동하는지를 출력하는 문제이다. 기본적으로 root값인 인덱스에 가까울수록 가장 적은 이동수를 제공한다. 예시는 아래와 같다. 값이 16이 있는 칸으로 움직여야할 때 (1,1) -> (1,16)15칸(0+15) 이동 (1,1) -> (2,8)8칸(1+7) 이동 (1,1) -> (4,4)6칸(3+3) 이동 따라서 (4,4)로 움직이는 것이 가장 적은 이동이고, 이동 칸 수는 6칸이다 이런 생각을 가지고 .. 2024. 2. 24.
SWEA D3 7584. 자가 복제 문자열 (python) 자가 복제 문자열 풀이 문제를 보고 문제에서 원하는 방향대로 해서 f함수와 g함수를 만들고 그것을 문제에서 제공한 풀이법 대로 풀어서 아래처럼 만들었다. # Pn을 구하기 위함 함수 def p_time(K): length_n = 1 n = 0 # 길이가 K보다 작을때만 while length_n < K: n += 1 length_n = length_n + 1 + length_n return n # 문자 반전 def f(A): tmp_A = "" for i in range(len(A)): if A[i] == '0': tmp_A += '1' else: tmp_A += '0' return tmp_A # 문자열 좌우 반전 def g(A): reverse_A = "" for j in range(len(A)-1,-.. 2024. 2. 21.
SWEA D3 19113. 식료품 가게 (python) 식료품 가게 풀이 할인 가격과 할인 전 가격이 같이 있는 리스트에서 할인 가격만을 추출해 내야 하는 문제이다. 오름차순으로 정렬해서 제공해주지만, 내가 풀이하는 방식으로는 내림차순으로 정렬해서 풀어야 문제가 풀리기에 재정렬을 해주었다. 풀이 계획은 아래와 같다. 내림차순으로 재정렬 while문을 시행. 할인 가격 즉, 0.75를 곱한 가격이 리스트에 있으면, 해당 인덱스를 찾아내서 pop()을 시행 후 answer 리스트에 입력 0.75를 곱한 가격이 리스트에 없으면 그것이 할인 가격이므로 해당 인덱스를 pop(), answer 리스트에 입력. 2와 3의 과정이 모두 끝난 후 answer는 내림차순으로 정렬되어 있는 리스트이므로, 이를 오름차순으로 형식에 맞게 출력하기 위해 for문 및 print(end.. 2024. 1. 30.
SWEA D3 19185. 육십갑자 (python) 육십갑자 풀이 흔히 아는 10 간과 12지를 결합하는 방식과 관련한 코드를 짜는 문제이다. 육 십간 자는 60년마다 회갑이 있기에 이를 기반으로 최소공배수를 구하여서 풀었다. N, M 의 최소공배수 구하기 gapja라는 리스트를 만들고 그 안에 회갑까지 가능한 모든 수를 넣기. 이제 찾으려는 년도에 % 연산자를 이용해서 gapja [인덱스]에 넣어서 구현 # 유클리드 호제법을 이용한 최소공배수 구하기 # 최소공약수 def gcd(a, b): while b != 0: a, b = b, a % b return a # 최소공배수 def lcm(a, b): return a * b // gcd(a, b) T = int(input()) for testcase in range(1, T+1): N, M = map(in.. 2024. 1. 30.
SWEA D2 1859. 백만 장자 프로젝트 (python) 백만 장자 프로젝트 풀이 연속된 N일 동안 물건의 매매가를 알고 있고, 이를 이용해 미리 사고파는 작업을 하려 한다. 당국의 감시망에 걸리지 않기 위해 1만큼 구입하고, 판매는 구매 후 언제든 가능. 원재가 얻을 수 있는 최대이익을 구하도록 하자. 몇 가지 방법을 했었는데, 제한시간 초과로 통과하지 못했었다. 앞에서 하는 방법 때문에 문제가 있나 싶어서 뒤에서부터 검사하기로 했다. 우선 반복문으로 모든 일자를 역순으로 돌았다. 이때 가장 큰 값을 찾아내며 돌았고, 만약 가장 큰 값인 max_value보다 이번 일자의 값이 더 작다면 그것을 이득으로 계산하기로 했다. 이러니 시간 초과 없이 해결되었다. T = int(input()) for testcase in range(1,T+1): earn = 0 da.. 2024. 1. 29.

티스토리툴바