본문 바로가기

알고리즘 풀이58

[백준/파이썬] 1463번: 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net import sys x = int(sys.stdin.readline()) # dp 테이블 d = [0 for _ in range(x+1)] for i in range(2, x + 1): # 1을 빼는경우 d[i] = d[i - 1] + 1 # 1을 뺄때와 3과 2로 나눌때 횟의 최솟값을 d[i]에 담는다 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[x]) 2023. 1. 10.
[백준/파이썬] 1003번 : 피보나치 함수 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net import sys t = int(sys.stdin.readline()) for _ in range(t): a = int(sys.stdin.readline()) if a == 0: print(1, 0) continue elif a == 1: print(0, 1) continue arr = [[0] * 2 for _ in range(a + 1)] arr[0] = [1, 0] arr[1] = [0, 1] for i in range(2, a + 1): arr[i] = [arr[i - 2][0] + .. 2023. 1. 9.
[백준/파이썬] 10773번 : 제로 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 입력 값이 0이 아닌경우 리스트에 추가. 0인경우 가장 마지막에 들어온 값을 삭제한다. import sys k = int(sys.stdin.readline()) arr = [] for _ in range(k): a = int(sys.stdin.readline()) if a != 0: arr.append(a) else: arr.pop() print(sum(arr)) 2023. 1. 9.
[백준/파이썬]1085번: 직사각형에서 탈출 https://www.acmicpc.net/problem/1085 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램 www.acmicpc.net import sys x, y, w, h = map(int, sys.stdin.readline().split()) print(min(x, y, w - x, h - y)) 4가지 방향으로의 거리를 계산해서 가장 작은값을 출력한다. 2023. 1. 9.
[백준/파이썬] 2869번 : 달팽이는 올라가고 싶다 https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net import math import sys a, b, v = map(int, sys.stdin.readline().split()) result = (v - b) / (a - b) print(math.ceil(result)) 다들 시도 해봤을 기본 풀이는 시간초과로 정답인정이 되지 않는다. 밤에 내려오는 거리를 고려하여 문제를 생각해야한다. 다른 블로그 참조. 2023. 1. 9.
[백준/파이썬] 1966번 : 프린터 큐 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net import sys t = int(sys.stdin.readline()) for _ in range(t): n, m = map(int, sys.stdin.readline().split()) # q = 중요도 q = (list(map(int, sys.stdin.readline().split()))) # arr = 순서 arr = list(range(len(q))) # 내가 원하는 순서 arr[m] = .. 2023. 1. 9.

티스토리툴바