본문 바로가기

PS109

[Baekjoon-Python] 1874 : 스택 수열 https://www.acmicpc.net/problem/1874 접근 수열을 순회하면서 해당 값까지 스택에 push한다. 스택을 pop하여 같은지 확인한다. 풀이 from sys import stdin def get_operator(nums): stack = [] operator = [] i = 1 for num in nums: while i 2024. 1. 14.
[Baekjoon-Python] 12886 : 돌 그룹 https://www.acmicpc.net/problem/12886 접근 전체 돌의 개수는 고정이므로 숫자 2개(a, b)만 사용한다. c = 전체 돌의 개수 - (a + b)로 구한다. 3개의 돌 그룹 중 2개를 선택해서 연산을 실행하고 큐에 추가한다. 중복된 a, b가 나올 수 있기 때문에 중복을 제거한다. 풀이 from sys import stdin from collections import deque def find_group(a, b): q = deque([(a, b)]) visited[a][b] = True while q: a, b = q.popleft() c = tot - a - b if a == b == c: return 1 for x, y in (a, b), (a, c), (b, c): .. 2024. 1. 14.
[Baekjoon-Python] 11058 : 크리보드 https://www.acmicpc.net/problem/11058 접근 N이 1 ~ 6일 경우 N만큼 A를 출력하는 것이 최댓값이다. 7부터는 붙여넣기를 한 번부터 세 번까지 시행한 것 중 최댓값을 선택한다. 풀이 from sys import stdin N = int(stdin.readline()) dp = [i for i in range(N + 1)] for i in range(7, N + 1): dp[i] = max(dp[i - 3] * 2, dp[i - 4] * 3, dp[i - 5] * 4) # (1) print(dp[N]) (1) dp[i - 3] * 2 : Ctrl-A, Ctrl-C, Ctrl-V dp[i - 4] * 3 : Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V dp[i -.. 2024. 1. 14.
[Baekjoon-Python] 2529 : 부등호 https://www.acmicpc.net/problem/2529 접근 0 ~ 9까지 순회하면서 dfs 탐색한다. 해당 숫자가 부등호를 만족하면 방문 처리한다. 만족하는 숫자를 모두 뽑으면(K + 1개) 최댓값과 최솟값을 갱신하고 탐색을 종료한다. 풀이 from sys import stdin def dfs(r, num): global min_result, max_result if r == K + 1: if int(min_result) > int(num): min_result = num if int(max_result) < int(num): max_result = num return for i in range(10): if visited[i]: continue if r == 0 or check_sign(s.. 2024. 1. 14.
[Baekjoon-Python] 1654 : 랜선 자르기 https://www.acmicpc.net/problem/1654 접근 랜선의 길이는 최대 231 - 1 (int형 최댓값 = 21억)이기 때문에 선형 탐색은 시간 초과가 발생한다. log2 (231 - 1) = 약 31이므로 이분 탐색으로 랜선의 길이를 구할 수 있다. low를 1, high를 가지고 있는 K개의 랜선 중 최대 길이로 설정한다. low와 high의 중간 값인 mid로 랜선을 잘라서 개수가 N보다 크거나 같은지 확인한다. (N개보다 많이 만드는 것도 N개를 만드는 것에 포함) N개를 만들 수 있으면 low = mid + 1, 만들 수 없으면 high = mid - 1로 설정한다. low가 high보다 작거나 같을 때까지 반복한다. K개의 랜선 중 최대 길이를 L이라고 할 때, 시간복잡도는.. 2024. 1. 14.
[Baekjoon-Python] 14888 : 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 접근 연산자 개수가 남아있으면 개수를 1 감소시킨 후 dfs 탐색한다. N만큼 탐색했으면 값을 저장하고 리턴한다. 호출이 끝났으면 연산자 개수를 다시 증가시킨다. 값을 오름차순 정렬하여 첫번 째와 마지막 인덱스 값을 출력한다. 시간복잡도는 O((N - 1)!) = 3,628,800이므로 브루트 포스 가능 풀이 from sys import stdin def dfs(idx, num): global add, sub, mul, div if idx == N: result.append(num) return if add > 0: add -= 1 dfs(idx+1, num + numbers[idx]) add += 1 if sub > 0: sub -= .. 2024. 1. 10.
[Baekjoon-Python] 1339 : 단어 수학 https://www.acmicpc.net/problem/1339 접근 알파벳마다 10^자릿수만큼 더한다. 내림차순으로 정렬하여 9부터 곱하면서 결과에 더한다. 풀이 from sys import stdin from collections import defaultdict alphabets_dict = defaultdict(int) for _ in range(int(stdin.readline())) : alphabets = stdin.readline().rstrip() for j in range(len(alphabets)) : alphabets_dict[alphabets[j]] += 10 ** (len(alphabets) - j - 1) scores = sorted(alphabets_dict.values().. 2024. 1. 10.
[Baekjoon-Python] 9020 : 골드바흐의 추측 https://www.acmicpc.net/problem/9020 접근 n을 2로 나누어 두 개의 숫자로 만든다. 두 수가 소수일 때까지 반복한다. 하나라도 소수가 아니면 1씩 더하고 뺀다. 풀이 from sys import stdin def is_prime(num) : if num == 1 : return False for i in range(2, int(num ** 0.5) + 1) : # (1) if num % i == 0 : return False return True T = int(stdin.readline()) for _ in range(T) : n = int(stdin.readline()) num1, num2 = n // 2, n // 2 while True : if is_prime(num1.. 2024. 1. 7.
[Baekjoon-Python] 4948 : 베르트랑 공준 https://www.acmicpc.net/problem/4948 접근 boolean 리스트를 선언한다. 소수가 아닌 값은 False 처리한다. n + 1 ~ 2n 인덱스를 슬라이싱하여 True 개수를 구한다. 풀이 1 from sys import stdin from math import sqrt arr = [True for i in range(123456 * 2 + 1)] for i in range(2, int(sqrt(123456 * 2)) + 1) : # (1) if arr[i] : j = 2 while i * j 2024. 1. 7.

티스토리툴바