Sangmun

17976번: Thread Knots (acmicpc.net) 17976번: Thread Knots Your program is to read from standard input. The input starts with a line containing one integer, n (2 ≤ n ≤ 100,000), where n is the number of threads. In the following n lines, the i-th line contains two integers xi (0 ≤ xi ≤ 109) and li (1 ≤ www.acmicpc.net * 이분 탐색으로 풀이하는 문제 import sys input = sys.stdin.readline n = int(input()) lines = ..

https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 다이나믹 프로그래밍으로 해결이 가능한 문제이며 또한 탐색해야되는 범위가 적기 때문에 2중 for문으로도 해결이 가능한 문제이다. 볼륨을 변경해야하는 단계마다 어떠한 볼륨으로 변경이 가능한지를 dp matrix에 저장을 해놓고 모든 경우의 수를 계산하해주면 된다. 문제의 예제 1번은 3 5 10 5 3 7 아래와 같은 형태로 dp matrix의 이전의 상태를 기..

https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net ' ', '+', '-'을 조합하여 만들 수 있는 수식중에서 0이 되는것을 찾는 문제이며 문제에서 제시되는 수의 범위가 굉장히 좁기 때문에 백트래킹을 이용하여 풀어도 시간내에 해결이 되는 문제이다. import sys input = sys.stdin.readline import copy t = int(input()) result = [] def backtracking(i): global s if i == n: s += str(i) tmp = copy..

https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 누수가 발생하는 지점을 리스트로 받고 오름차순으로 정렬을 해주어 가장 가까운 누수지점부터 차례로 테이프를 붙여가면서 테이프의 길이를 넘어갈때 개수를 하나씩 추가해주면 된다. import sys input = sys.stdin.readline n, l = map(int,input().split()) leak_point = list(map(int,input().split())) lea..

https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 그리디 알고리즘을 이용하면 쉽게 풀 수 있는 문제이다. 단순히 기타줄 세트와 낱개의 가격에서 가장 저렴한 비용만을 이용하면 쉽게 해결이 되는 문제이다. 최소가격을 결정하는 케이스는 3개뿐이라 3개의 케이스를 모두 계산을 해서 다시 최소값을 구하면 되는 문제이다. import sys input = sys.stdin.readline n, m = map(int,input().split()) set_..

https://animoto1.tistory.com/entry/%EB%B0%B1%EC%A4%80-11057-%EC%98%A4%EB%A5%B4%EB%A7%89-%EC%88%98-%ED%8C%8C%EC%9D%B4%EC%8D%AC-Python [백준] 11057 오르막 수 (파이썬 Python) https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이 animoto1.tistory.com # 11057 n = int(input()) dp = [1]*10 for i in range(1,n) : for j in ran..

https://infinitt.tistory.com/250 N = int(input()) p = [0] + list(map(int,input().split())) dp = [0 for _ in range(N+1)] for i in range(1,N+1): for k in range(1,i+1): print(i,k) dp[i] = max(dp[i], dp[i-k] + p[k]) print(dp[N])

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net stack을 활용한 문제이다. 그냥 외워도둬 굉장히 괜찮을 문제이다. import sys input = sys.stdin.readline string = str(input().strip()) bomb = str(input().strip()) lastChar = bomb[-1] stack = [] length = len(bomb) for char in string: stack.appe..