성공을 즐기자

https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 코드는 맞는 것같은데 시간초과가 난다....😥 시간초과 코드 : def dfs(L,val) : if L == n : candi.add(abs(val)) else : dfs(L+1,val+goosle[L]) dfs(L+1,val-goosle[L]) dfs(L+1,val) if __name__=="__main__" : n = int(input()) goosle = list(map(int,input()...

문제에서 적어도 c명을 늘리는 것이므로 더 많이 늘리는 것도 생각을 해주어야 하기 때문에 dp의 크기를 c+100으로 한다. 100의 이유는 100명보다 작거나 같게만 고객의 수가 비용에 따라 증가할 수 있기 때문이다. 입력받은 (비용과 고객의 수)리스트를 돈다. (첫번째 for문) 입력받은 고객의 수에서 시작해서 dp리스트의 끝까지 돈다. (두번째 for문) 최소 고객의 수보다 작게는 증가를 못시키기 때문이다. dp[i]의 의미는 i 명을 증가시키는데 필요한 돈의 최솟값이다. 점화식 : dp[i] = min(dp[i-custo] + cost , dp[i]) 고객을 custo 만큼 늘린 대신 cost를 더한 값과 원래 값중에서 더 저렴한 값으로 갱신한다. i가 원했던 고객의 수 보다 크보다 같은 경우 값..

상황을 잘 나눠서 상황에 따라 잘 계산해줘야한다. dy[j]의 의미는 j번째 문자열까지 연산했을 때 연산의 최댓값이다. 코드 : if __name__=="__main__" : a = list(input()) dy= [-int(1e9)]*(len(a)) # dy[j] : j가 마지막 숫자일 때의 최대 계산 결과 # 글자가 한글자라면 숫자로 해석 if len(a) ==1 : if a[0] == '+' : print(10) else : print(1) # 글자가 여러 글자라면 else : # 첫 글자 - 은 연산자가 아님 if a[0] == '-' : dy[0] = 1 else : dy[0] = 10 # 이왕이면 큰 숫자를 얻는게 좋음 if a[1] == '-' : dy[1] = 11 # 나머지 숫자들을 돌면..

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 왼쪽 전봇대 번호 순으로 정렬을 한 후 오른쪽 전봇대의 가장 긴 증가하는 순열의 길이를 구하면 된다. 구한 순열의 길이는 겹치지 않고 설치할 수 있는 전깃줄의 길이이므로 전체 전깃줄의 개수에서 구한 길이를 빼주면 제거해야하는 전깃줄의 길이가 나온다. 코드 : if __name__=="__main__" : n = int(input()) arr = [list(map(int,input().split()))fo..

점수를 저장할 score 리스트 , dp값을 저장할 리스트를 만든다. 들어오는 계단의 개수가 1,2,3 일때는 하드코딩을 해준다. 그 이상일 때는 for문을 돌면서 dp 배열을 채워준다. 조건에는 한 계단 혹은 두 계단씩 오를 수 있다는 조건이 있다. 그리고 마지막 도착 계단은 반드시 밟아야 한다. 마지막 계단을 밟고 2단계 이전 계단을 밟는 경우와 (score[i] + dp[i-2] ) 마지막 계단과 바로 이전 계단 그리고 2단계 이전 계단을 밟는 경우가 있을 수 있다. (score[i] + score[i-1] + dp[i-3]) 코드 : if __name__=="__main__" : score = [] dp = [] l = int(input()) score.extend(list(int(input())..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 코드 : N,K = map(int,input().split()) items = [] dp = [0 for _ in range(K+1)] for i in range(N): w,v = map(int,input().split()) for j in range(K,w-1,-1): dp[j] = max(dp[j],dp[j-w]+v) print..

https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 문제 설명 : 왼쪽 그림과 같이 진행된다. (1,1)에서 시작하여 우측, 아래로 이동한다. 경로의 개수를 반환하는 것으로 왼쪽과 위의 합을 새로운 값으로 지정한다. 중간에 웅덩이는 무시하고 넘어간다. 도착 위치의 값을 반환하면 된다. 코드 : def solution(m, n, puddles): answer = 0 # puddle 이 (m,n)으로 주어..

문제 : https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 코드 : def solution(triangle): answer = 0 for i in range(1, len(triangle)) : for j in range(len(triangle[i])) : if j == 0 : # 왼쪽 끝 원소 triangle[i][j] += triangle[i-1][j] elif j == len(triangle[i])-1 : # 오른쪽 끝의 원소 triangle[i][j] += triangle[i-1]..

https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 코드 : def solution(N, number): answer = -1 dp = [] for i in range(1,9) : # N을 i번 사용 all_case = set() check_number = int(str(N)*i) #N 반복 (i 번 만큼) all_case.add(check_number) for j in range(0,i-1) : # dp에는 i-1만큼이 있음 for op1 in dp[j] : for op2 in dp[-j-1] : all_case.add(op1 - op2) all_case.add(op1 + op2) all_..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 이 문제는 LIS(최장 증가 부분 수열)으로 이와 비슷한 백준문제(같이 풀면 좋을 문제)에는 가장 긴 감소하는 부분 수열 [11722번] 가장 긴 바이토닉 바이토닉 부분 수열 [11054번] 상자넣기[1965번] 전깃줄[2565번] 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개..