아이테킨의 끄적끄적

다이나믹 프로그래밍 문제는 점화식을 풀어서 해결해야 하는 경우가 많다는 것을 기억하자. 이 문제도 점화식을 사용해보면 해결할 수 있다. i번째 포도주를 시음한다고 하면 생각할 수 있는 경우의 수는 1. i-2번째 포도주를 마신 경우 2. i-3번째 i-1번째 포도주를 마신 경우 또한 i번째 포도주를 마시지 았았을 경우 생각할 수 있는 경우의 수는 3. i-1번째 포도주를 마신 경우이다. 이 세가지 경우의 수 에서 가장 큰 값을 출력해내면 된다. 이를 점화식으로 표현해보면 dp[i] = max(dp[i-2]+w[i], dp[i-3]+w[i-1]+w[i], dp[i-1]) # 2156번: 포도주 시식 # dp문제는 점화식을 만들어봐야 한다. # 다시 풀어보기!! 아 실력이 안느냐 왜 ㅠㅠ n = int(in..

그리디문제로 나는 행렬이 들어가기만 하면 어렵다 ㅠㅠ # 1080번: 행렬 # 다시풀기 n,m = map(int,input().split()) graph1 = [] graph2 = [] cnt = 0 def convertgraph(i,j): for x in range(i,i+3): for y in range(j,j+3): graph1[x][y] = 1- graph1[x][y] for i in range(n): graph1.append(list(map(int,input()))) for i in range(n): graph2.append(list(map(int,input()))) for i in range(n-2): for j in range(m-2): if graph1[i][j] != graph2[i][j..

그리디 문제로 발생할 수 있는 경우의 수를 차근차근 따져보면서 풀어보면 된다. 우선 이 문제는 사야하는 줄보다 더 많이 사도 된다는 것이 포인트이다. 그래서 6개 세트로 넉넉하게 살 경우 1개를 낱개로 맞춰서 사는 경우보다 저렴할 경우 넉넉하게 사도 된다. 또 놓치지 말아야 할 부분은 6개 세트가 낱개로 6개를 살때보다 항상 싸다는 말은 없다. 따라서 이 부분도 신경을 써주어야 한다. 이를 코드로 표현하면 아래와 같다. # 1049번 기타줄 n,m = map(int,input().split()) line_set = [] line_ = [] for i in range(m): a,b = map(int,input().split()) line_set.append(a) line_.append(b) e = min(..

쉬운 문제인듯 하다 정답률도 높다.(70퍼 이상) 최소값을 만들땐 6을 5로 바꿔주고 최대값을 만들땐 5를 6으로 바꿔주면 된다. # 2864번: 5와 6의 차이 a,b = map(int,input().split()) min_a = '' for i in str(a): if i == '6': min_a += '5' else: min_a += i min_b = '' for i in str(b): if i == '6': min_b += '5' else: min_b += i max_a = '' for i in str(a): if i == '5': max_a += '6' else: max_a += i max_b = '' for i in str(b): if i == '5': max_b += '6' else: max..

# 1912번: 연속합 n = int(input()) a = list(map(int, input().split())) sum = [a[0]] for i in range(len(a) - 1): sum.append(max(sum[i] + a[i + 1], a[i + 1])) print(max(sum))

이분탐색(binary search)를 이용해서 풀었다. 이분탐색은 탐색 기법중 하나로 말 그대로 탐색범위를 두 부분으로 나눠서 원하는 값을 찾는 방식이다. 탐색 범위를 절반씩 줄여가면서 찾는 탐색방법이다. 따라서 시간복잡도가 하나하나 일일이 탐색하는 순차탐색보다 더 좋다. 시간복잡도 : O(logN) 이분탐색을 할 때는 먼저 정렬이 된 상태이어야 한다. dynamic programming, recursion의 개념이 녹아있다. 이분탐색 함수를 따로 정의해주고 찾아야할 리스트는 파이썬 함수로 정렬해주었다. # 10815번: 숫자 카드 n = int(input()) n_list = list(map(int,input().split())) m = int(input()) m_list = list(map(int,i..

A에서 B를 만드는것이 아니라 반대로 B에서 A를 만드는 방향으로 생각해서 풀었다. B를 10으로 나눈 값이 1 이거나 B가 2로 나누어떨어질때마다 카운트를 계속 해주고 B가 A보다 작거나 위의 조건을 만족시키지 못하는 수(한자리 홀수)가 나오면 카운트를 -1로 정의해주면 된다. 처음 풀 때 한자리 홀수를 생각하지 않고 단순히 b B a,b = map(int,input().split()) cnt = 1 while True: if b == a: break elif (b%2 != 0 and b % 10 != 1) or (b

DP문제로 이 문제는 뒤에서부터 생각해야 풀 수 있다. 뒤에서 풀어보려고 계속 노력하다가 결국엔 다른 사람의 블로그를 참고해서 풀었다. 참고 블로그 https://pacific-ocean.tistory.com/199 # 14501번: 퇴사 n = int(input()) t_list = [] p_list = [] for _ in range(n): t,p = map(int,input().split()) t_list.append(t) p_list.append(p) dp = [0]*(n+1) for i in range(n-1,-1,-1): if t_list[i] + i > n: dp[i] = dp[i+1] else: dp[i] = max(dp[i+1],p_list[i] + dp[i + t_list[i]]) pr..

DP문제다 DP문제의 가장 큰 특징은 중복되는 서브문제(overlapping subproblem)와 최적 부분 구조(optimal substructure)로 이런 유형의 문제에 접근하기 위해서는 하나의 문제를 작은 그러나 같은 방법으로 풀 수 있는 문제로 쪼개야한다. 이번 문제에서는 원하는 카드의 개수를 만드는 최대값을 구해야한다. 카드 1개 샀을때 최대값 카드 2개 샀을때 최대값 카드 3개 샀을때 최대값 카드 4개 샀을때 최대값 이런식으로 생각을 해보면 카드 1개 -> P[1] (=1개 카드 값) 카드 2개 -> max(P[1]+P[1] , P[2]) 카드 3개 -> max(P[1]+P[1]+P[1] , P[1]+P[2] , P[3]) ... 이런식으로 모두 따져봐야 하는 문제다. #11052번: 카드..

앞서 풀었던 타일 문제에 정사각형 타일이 하나 추가된 문제이다. 정사각형 모양의 타일이 하나 추가되었기 때문에 n-2번째 타일에서 가로 직사각형 두개 붙이는 경우와 정사각형 붙이는 경우, 총 두가지 방법으로 늘어났다. m(n) = m(n-1) + (2 × m(n-2)) # 11726번: 2xn 타일링 n = int(input()) m = [0]*1001 m[1] = 1 m[2] = 2 for i in range(3,n+1): m[i] = m[i-1] + m[i-2] print(m[n]%10007)