흙금이네 블로그

아이디어 아이들 수에서 최장 증가 부분 수열의 길이를 뺀다. 풀이 리스트 child에 아이들의 번호를 입력 받아 저장하고, 1로 채워진 N 길이의 리스트 dp를 만든다. 이중 for문에서 j번째 아이의 번호가 앞에 있는 i번째 아이 번호보다 크면 증가 부분 수열 길이를 비교해 갱신한다. 마지막에 아이들 수 N에서 최장 증가 부분 수열의 길이를 빼서 출력한다. import sys N = int(input()) child = list(map(int, sys.stdin.readlines())) dp = [1]*N for i in range(N-1): for j in range(i+1, N): if child[i] < child[j] and dp[j] < dp[i]+1: dp[j] = dp[i]+1 print(..

아이디어 DFS로 주어진 연산자로 가능한 식을 만들어 그 최댓값과 최솟값을 찾는다. 풀이 #1 (Python) 덧셈, 뺄셈, 곱셈, 나눗셈을 수행하는 람다식들을 리스트 cal에 저장한다. 리스트 operator에 각 연산자의 개수를 저장하고, 최댓값과 최솟값을 저장하는 리스트 res를 생성한다. 함수 dfs에서는 재귀 호출로 주어진 연산자를 사용하여 식을 만들고, 식을 모두 만들면 결과값과 비교하여 갱신해 나간다. cal = [lambda a, b: a+b, lambda a, b: a-b, lambda a, b: a*b, lambda a, b: a//b if a > 0 else -(-a//b)] def dfs(idx, total, a, s, m, d): global res if idx >= N: if t..

아이디어 동적 계획법으로 암호를 구성하는 숫자들이 직전의 숫자와 붙을 수 있는지 여부를 확인하여 가짓수를 구한다. 풀이 10과 20을 제외하고 0으로 시작하거나 30처럼 0이 포함된 암호는 해석할 수 없으므로 0을 출력한다. elif문에서 0이 아니면서 N의 길이가 1인 암호는 1을 출력한다. 그 외의 경우는 1로 채워진 N+1 길이의 리스트 dp를 생성하고, for문에서 암호를 구성하는 숫자들을 차례로 확인한다. 만약 현재 숫자가 0인 경우 직전 숫자와 붙여야 하므로 앞의 숫자 이전의 경우로 되돌린다. 직전 숫자가 0이 아니면서 현재 숫자를 직전 숫자와 붙일 수 있으면 직전 숫자까지의 가짓수와 그 이전 가짓수를 더한다. 그 외에 직전 숫자와 붙일 수 없는 경우는 직전 숫자까지의 가짓수로 저장한다. co..