www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net (풀이) 시간 제한이 0.5초이기 때문에 평소처럼 반복문에서 일일이 비교하면 시간 제한으로 틀릴 수 있다. 투포인터 알고리즘을 이용해서 풀었는데 만약 끝(end)이 n과 같아져서 풀이를 끝내면 end는 그대로 있고 start가 증가 할 경우를 빠뜨릴 수 있기 때문에 start, end, n 이 세가지가 같아질 경우 반복문이 끝내게 만들었다. 또한 반복문 안에서 합이 m보..
www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 일곱 숫자의 합이 100이 되며 고정적으로 9개의 숫자를 입력 받으니 전체 합에서 두개를 뺀 값이 100이 되면 된다. 당연히 7개의 숫자를 더하는 코드를 짜는 것보다 100이 되게 빼는 2개의 숫자를 구하는 것이 간단하다. import sys input = sys.stdin.readline arr = list() result_arr = list() for i in range(9): arr.append(int(input..
www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 딜러가 외치는 m보다 작은 최대합을 구하는 문제이다. 배열안에서 세 개의 수를 골라 합을 구하면 되므로 for문을 3개사용해서 답을 구했다. 아무래도 for문이 3개 쓰이다 보니 시간복잡도가 커서 틀릴 줄 알았는데.. 맞았다..!? import sys input = sys.stdin.readline n,m = map(int,input().split()) arr = list(map..
www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 일단, 최대 세자리 수가 입력이 되므로 1부터 999까지를 생각하고 풀면 된다. 근데 여기서, 1~9 즉 한자리 수는 한수인가.. 아닌가..를 고민했는데 찾아보니 한수였다! 그러므로 1부터 99까지는 모두 한수가 될것이며 조건문으로 한수를 확인해야할 부분은 세자리 수이다. 한 수씩 리스트에 담아서 그 차이를 비교하면 풀 수있는 문제였다. import sys input = sys.stdin.readline num =..
www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net n 번째의 타일리을 위해서는 세가지 경우가 존재한다. (1) n-1 번까지의 타일링 이후 2x1 타일을 붙이는 경우 (2) n-2 번까지의 타일링 이후 1x2 타일을 두개 붙이는 경우 (3) n-2 번까지의 타일링 이후 2x2 타일을 한개 붙이는 경우 그러므로 이러한 세가지 상황을 모든 경우의 수로 따져 코드를 작성해 보면 다음과 같다. import sys input = sys.stdin.readline n = int(input()) d =..
www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net import sys input = sys.stdin.readline n,m = map(int,input().split()) graph = [] for i in range(n): graph.append(list(map(int,input().split()))) dp = [[0] * (m+1) for _ in range(n+1)] for i in range(1,n+1): for j in range(1,..
