Sangmun

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/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://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 기하학의 기본적인 문제라고 한다. 푸는 방법이 이미 널리 알려진 듯 하다. https://www.acmicpc.net/blog/view/27 점 3개의 방향성을 나타내는 CCW 세 점 P1(x1, y1), P2(x2, y2), P3(x3, y3)가 있을 떄, 점 3개를 이은 선분은 어떤 방향성을 나타내게 될까요? 11758번 문제..

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net n의 케이스가 0 1: graph[a][b] = 0 # 결과 출력 for a in range(n): result = map(str,graph[a]) print(' '.join(result))