[백준] 1912번 - 연속합 (한줄평) 점화식을 세우는데 헷갈리긴 했지면 결국 혼자서 풀어낸 문제! 나중에 한번쯤 복습해보면 좋을 것 같다~ 풀이 시간: 20분 이내 1) 문제 해결 아이디어 크기가 n인 수열에서 연속된 몇 개의 수를 선택해서 구할 수 있는 합의 최댓값을 구하는 문제다. 처음에 이 문제가 헷갈렸던 이유는 i번째 원소(graph[i])를 포함 시키는 경우, 포함 시키지 않는 경우 2가지로 나눠야한다고 생각했기 때문이다. 그래서 자꾸 이상한 답이 나왔다... 이 문제에서 중요한 점은 연속된 숫자를 선택한다는 것이고 최소 1개이상의 수를 선택해야 한다는 점이다. 1. i번째 원소 선택, (i -1)번째 원소 선택한 경우, (i - 2)번째는 선택할 수도 있고 안할 수도 있다. 그러므로 i번째..
[백준] 2565번 - 전깃줄 (한줄평) 최장 증가 부분 수열과 유사한 문제라고 생각했지만 막상 잘 해결이 안됐던 문제.. 복습이 필요하다!! 유사 문제: 11053 https://hseungyeon.tistory.com/304 [다이나믹 프로그래밍] ▲ 11053번 - 가장 긴 증가하는 부분 수열 [백준] 11053번 - 가장 긴 증가하는 부분 수열 (한줄평) 풀었던 문제지만 다시 풀려니 기억이 잘 안나서 어려웠던 문제.. 꼭 복습이 필요하다!!! 풀이 시간: 30분 이내 유사 문제: https://hseungyeon.ti hseungyeon.tistory.com 풀이 시간: 30분 이내 1) 문제 해결 아이디어 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 ..
[백준] 11726번 - 2xn 타일링 (한줄평) 쉽게 해결할 수 있었던 문제! 유사 문제: https://hseungyeon.tistory.com/287 [다이나믹 프로그래밍] ▲ 문제3 - 바닥 공사(223p) [이코테] 문제3 - 바닥 공사(223p) (한줄평) 코드는 짧으나 점화식을 떠올리기가 쉽지 않았던 문제로 복습이 꼭 필요!! 풀이 시간: 30분 이내 1) 문제 해결 아이디어 가로 길이: n, 세로 길이: 2 인 직 hseungyeon.tistory.com 풀이 시간: 10분 이내 1) 문제 해결 아이디어 가로 길이: n, 세로 길이: 2 인 직사각형 바닥을 1*2, 2*1 2가지 타일로 채울 수 있는 경우의 수를 10007로 나눈 나머지를 구하는 문제다. 이 문제는 다이나믹 프로그래밍의 기..
[백준] 11054번 - 가장 긴 바이토닉 부분 수열 (한줄평) LIS 응용 문제로 LIS(최장증가부분수열)알고리즘을 안다면 쉽게 풀 수 있었던 문제! 풀이 시간: 15분 이내 1) 문제 해결 아이디어 n이 1이상 1000이하인 길이가 n인 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 구하는 문제다. 수열 S가 어떤 수 Sk를 기준으로 (S1 Sk+1 > ... SN-1 > SN)을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. Sk를 기준으로 왼쪽은 가장 긴 부분 증가 수열, 오른쪽은 가장 긴 부분 감소 수열을 구하면 풀 수 있는 문제다. 가장 긴 부분 감소 수열을 구하기 위해서 입력받은 수열을 reverse해야한다는 것을 잊지말자! 2) 소스코드 n = int(input()) # ..
[백준] 11053번 - 가장 긴 증가하는 부분 수열 (한줄평) 풀었던 문제지만 다시 풀려니 기억이 잘 안나서 어려웠던 문제.. 꼭 복습이 필요하다!!! 풀이 시간: 30분 이내 유사 문제: https://hseungyeon.tistory.com/290 [다이나믹 프로그래밍] ★ 문제6 - 병사 배치하기(59:50) [이코테] 문제6 - 병사 배치하기(59:50) (한줄평) 아이디어를 떠올리기 어려웠던 문제로 답을 봤음에도 이해하는데 어려움이 있어서 꼭 복습이 필요!! 풀이 시간: 1) 문제 해결 아이디어 예를 들어 hseungyeon.tistory.com 1) 문제 해결 아이디어 1이상 1000이하의 크기인 수열 A가 주어졌을 떄 수열 A의 가장 긴 증가하는 부분 수열의 길이를 구하는 문제다. 저번에 ..
[백준] 2156번 - 포도주 시식 (한줄평) 점점 dp문제 감을 찾는 것 같다고 느껴진 문제! 유사 문제: 2579 https://hseungyeon.tistory.com/300 [다이나믹 프로그래밍] ▲ 2579번 - 계단 오르기 [백준] 2579번 - 계단 오르기 (한줄평) 조건때문에 계속 헷갈려서 생각보다 어려웠던 문제! 코드는 단순하지만 복습이 필요하다!! 풀이 시간: 40분 이내 1) 문제 해결 아이디어 다음 조건을 만족하 hseungyeon.tistory.com 풀이 시간: 10분 이내 1) 문제 해결 아이디어 2가지 조건을 만족하며 n개의 포도주 중 최대로 마실 수 있는 포도주의 양을 구하는 문제다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치..
[백준] 10844번 - 쉬운 계단 수 (한줄평) 생각보다 빨리 아이디어가 떠올라 쉽게 풀 수 있었던 문제! 2차원으로 접근해야한다는 것을 깨달으면 쉽게 풀 수 있다. 한번쯤 복습해보면 좋을 것 같은 문제 풀이 시간: 20분 이내 1) 문제 해결 아이디어 인접한 모든 자리의 차이가 1인 수를 계단수라고 한다. (단, 0으로 시작하는 수는 계단수가 아니다) 1이상 100이하의 자연수 n이 주어질 때, 길이가 n인 계단 수의 총 개수를 구하는 문제다. 길이가 n인 계단 수의 마지막 숫자는 0 ~ 9 사이의 수로 10가지 경우가 있다. 길이가 n, 마지막 숫자가 j인 계단 수의 개수 = 길이가 (n - 1)인 계단수 중 j - 1, j + 1 로 끝나는 계단수의 개수의 합이다. 그러므로 길이가 n인 계단수의 ..
[백준] 1463번 - 1로 만들기 (한줄평) 전에 풀었던 문제와 유사하지만 생각보다 시간이 좀 걸렸던 문제! 유사 문제: https://hseungyeon.tistory.com/285 [다이나믹 프로그래밍] ▲ 문제1 - 1로 만들기(217p) [이코테] 문제1 - 1로 만들기(217p) (한줄평) 평소였으면 최소값을 구하는 문제니 BFS로 해결 했을테지만 전형적인 다이나믹 프로그래밍 문제! 추후 복습이 꼭 필요한 문제 풀이 시간: 40분 이내 1) hseungyeon.tistory.com 풀이 시간: 20분 이내 1) 문제 해결 아이디어 정수 X(1
