https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net # 조건 주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을지 구하라 크기가 10x10이고 총 100개의 칸으로 나누어져 있다. 플레이어가 i번 칸에 있고, 나온 수가 4라면, i+4번으로 이동해야한다. 결과가 100번을 넘어간다면 이동할 수 없다. 도착한 칸이 사다리면, 사다리를 타고 위로 올라간다. ..

http://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net # 조건 수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열을 구하라 # 접근 방법 이전의 하위 문제처럼 DP를 이용하여 이전 값들을 모두 순회한다면 수열 A의 크기 1,000,000 이하 이므로 시간초과가 난다. 따라서, 현재 값들을 dp테이블에 추가해주며, dp에서 가장 큰 수보다 크다면 append, 아니라면 들어갈 수 있는 자리를 찾아서 넣어준다. 찾는 모듈은 bisect를 이용해준다. im..

http://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net # 조건 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하라 A = {10, 20, 10, 30, 20, 50} 인 경우 가장 긴 증가하는 부분 수열은 10, 20, 30, 50 이고 길이는 4이다. # 접근 방법 dp를 이용해준다. 현재 인덱스의 숫자를 기준으로 이전의 숫자를 모두 훑어 준다. 1번부터 채워가..

http://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net # 조건 N개의 자연수와 자연수 M이 주어질 때 아래 조건 만족하는 길이가 M인 수열 모두 구하라. N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순 # 접근 방법 자기 자신과의 선택도 가능하므로 중복조합 이용해준다. combinations_with_replacement from itertools import combinations_with_r..

http://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net # 조건 N개의 자연수와 자연수 M이 주어질 때, 아래 조건 만족하는 길이가 M인 수열을 모두 가하라 N개의 자연수 중에서 M개를 고른 수열 # 접근 방법 중복되는 수열 여러 번 출력하면 안되지만 순서가 뒤바뀐 것은 다른 수열이므로 순열을 이용해준다. 사전 순 출력이므로 오름차순 from itertools import permutations N, M = map(int, input().spl..

http://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net # 조건 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하라 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1

http://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net # 조건 N x N 크기의 공간에 물고기 M마리와 아기 상어 1마리 한 칸에는 물고기가 최대 1마리 존재 아기 상어와 물고기는 모두 크기를 가지고 있고, 크기는 자연수이다. 최초의 아기 상어 크기 = 2, 1초에 상하좌우로 인접한 한 칸씩 이동 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 못 지나가고, 나머지 칸은 모두 지나간다. 이 때, 크기가 같은 물고기는 먹을 수 없지만, 있는 ..

http://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 조건 nCm 을 구하여라 접근 방법 입력이 크지 않기 때문에 dp 이용해주지 않아도 될 것 같다. def fac(n): num = 1 for i in range(2,n+1): num*=i return num n,m = map(int,input().split()) print(fac(n) // (fac(m)*fac(n-m)))

http://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net # 조건 n가지 종류의 동전이 있고 각각의 동전이 나타내는 가치는 다르다. 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶을 때, 그 경우의 수를 구하시오 각 동전은 몇 개라도 사용 가능하다. 동전의 구성이 같은데, 순서만 다른 것은 같은 경우 # 접근 방법 다이나믹 프로그래밍을 이용해서 풀어주면 될 것 같다. 가치의 합 +1 만큼의 dp테이블을 만들어 주고 각 가치를 만들 수 있는 ..