문제 (링크) https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 나의 풀이 n = int(input()) d = [0] * 1000001 for i in range(2, n+1): d[i] = d[i-1] + 1 if i % 2 == 0: d[i] = min(d[i], d[i//2] + 1) if i % 3 == 0: d[i] = min(d[i], d[i//3] + 1) print(d[n]) 나동빈님의 유튜브 이.코.테 다이나믹 프로그래밍 강의를 들은 후 연습 문제로 풀어보았다. 사실 유튜브에서 제공한 연습문제랑 연산 조건만 다를 뿐 아예 같은 문제라고 봐도 ..
알고리즘/문제풀이
문제 (링크) https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 나의 풀이 n = int(input()) data = list(map(int, input().split())) count = 0 for x in data: for i in range(2, x+1): if x % i == 0: if x == i: count += 1 break print(count) 백준에서 틀린 문제를 살펴보다가 발견한 문제다. 왜 그랬는지는 모르겠는데 꽤 많이 틀려놨었고, 발견하자마자 풀어봤는데 바로 풀렸다. 알고리즘 문제 중 소수와..
문제 (링크) https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 나의 풀이 from sys import stdin n = stdin.readline() # 이진탐색을 진행해야하므로 탐색을 할 리스트를 sorted 처리 해준다 group_n = sorted(list(map(int, stdin.readline().split()))) m = stdin.readline() group_m = list(map..
문제 (링크) https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 나의 풀이 from collections import deque n, m = map(int, input().split()) graph = [] # 상 하 좌 우 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] for _ in range(n): graph.append(list(map(int, input()))) def bfs(x, y): queue = deque() queue.append((x, ..
문제 (링크) https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 나의 풀이 from collections import deque n, m, v = map(int, input().split()) matrix = [[0] * (n+1) for _ in range(n+1)] visited = [False] * (n+1) for _ in range(m): a, b = map(int, input().split()) m..
문제 (링크) https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 나의 풀이 from itertools import combinations n, m = map(int, input().split()) items = list(map(int, input().split())) comb = list(combinations(items, 3)) # combinations를 이용해 나열 가능한 조합 만들기 sum_value = [..
문제 (링크) https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 나의 풀이 n = int(input()) s = [] # 스택 for _ in range(n): x = int(input()) if x != 0: s.append(x) else: s.pop() print(sum(s)) 문제에 나오는대로 append와 pop만 사용하면 되는 문제
문제 (링크) https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 나의 풀이 n = int(input()) data = list(map(int, input().split())) data.sort() # 걸리는 시간을 오름차순으로 정렬했을 때 최솟값이 나온다 waiting_time = [] for i in range(n): waiting_time.append(sum(data[:i+1])) # 걸리는 시간을 인덱싱한 후 sum한 값을 waiting_time에 추가 print(sum..
