Problem Solving/Baekjoon
-
[백준] 1748번 문제 (수 이어 쓰기 1) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 8. 25. 11:49
https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net n = int(input()) n_len = len(str(n)) count = 0 # 자리수 기반으로 개수를 구함 for i in range(n_len - 1): count += 9 * 10 ** i * (i + 1) # 자리수를 구하고 나머지 숫자를 구하고 출력 print(count + (n - 10 ** (n_len - 1) + 1) * n_len) 규칙이 있을 것이라 생각했지만 찾지는 못 했고 다른 사람의 풀이를 참고했다. 숫자 n에 대한 규칙은 다음과 같다. 자리수 1개인 경우에는 숫자가 1 ~ 9이고 1 ~..
-
[백준] 1107번 문제 (리모컨) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 8. 23. 14:29
https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net import sys input = sys.stdin.readline n = int(input()) m = int(input()) useless_buttons = list(input().strip()) result = abs(n - 100) def is_exist(num): nums = list(str(num)) for n in nums: if n in useless_buttons:..
-
[백준] 2309번 문제 (일곱 난쟁이) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 8. 23. 13:36
https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net heights = sorted([int(input()) for _ in range(9)]) sum_heights = sum(heights) for i in range(8): for j in range(i + 1, 9): if sum_heights - (heights[i] + heights[j]) == 100: x1, x2 = heights[i], heights[j] heights.remove(x1) hei..
-
[백준] 1476번 문제 (날짜 계산) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 8. 23. 13:26
https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net e, s, m = map(int, input().split()) s1, s2, s3, year = 1, 1, 1, 1 while e != s1 or s != s2 or m != s3: s1 += 1; s2 += 1; s3 += 1; year += 1 if s1 > 15: s1 = 1 if s2 > 28: s2 = 1 if s3 > 19: s3 = 1 print(year) 브루트포스 문제라 단순하고, 무..
-
[백준] 10451번 문제 (순열 사이클) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 8. 23. 13:19
https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net import sys sys.setrecursionlimit(10**7) input = sys.stdin.readline def dfs(start, visited): visited[start] = True for i in graph[start]: if not visited[i]: dfs(i, visited) for _ in r..
-
[백준] 11724번 문제 (연결 요소의 개수) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 8. 23. 10:49
https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net import sys sys.setrecursionlimit(10**7) input = sys.stdin.readline n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] visited = [False] * (n+1) for _ in range(m): v1, v2 = m..
-
[백준] 1850번 문제 (최대공약수) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 8. 23. 10:24
https://www.acmicpc.net/problem/1850 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net # 최대 공약수 (재귀) def gcd(a, b): if b == 0: return a else: return gcd(b, a % b) 처음에는 위와 같은 방식으로 최대 공약수를 구했으나 재귀적으로 최대 공약수를 구하기 때문에 메모리 초과가 났다. 따라서 아래와 같이 최대 공약수를 구하는 방법을 바꾸었고, 통과를 할 수 있었다. def gcd(a, b): while b: a,..
-
[백준] 1158번 문제 (요세푸스 문제) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 8. 20. 15:52
https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net from collections import deque import sys n, k = map(int, sys.stdin.readline().split()) dq = deque([i+1 for i in range(n)]) result = [] while dq: dq.rotate(-(k-1)) result.append(str(dq.popleft())) sys.stdout.write("") deque의 rotate라는 함수를 유용하게 사용한 문제였다. 받은 숫자를 deque 형태로 저장하고 r..
-
[백준] 11004번 문제 (K번째 수) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 8. 20. 15:35
https://www.acmicpc.net/problem/11004 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net from sys import stdin n, k = map(int, stdin.readline().split()) nums = list(map(int, stdin.readline().split())) print(sorted(nums)[k - 1]) 정렬을 해서 해당 인덱스로 출력만 하면 되는 아주 간단한 문제다.
-
[백준] 11652번 문제 (카드) 파이썬(Python) 풀이Problem Solving/Baekjoon 2021. 8. 20. 15:15
https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net from collections import Counter from sys import stdin cards = [] for _ in range(int(stdin.readline())): cards.append(int(stdin.readline())) counted_cards = sorted(Counter(cards).most_common(), key=lambda x: (-x[1], x[0])..