2019 winter PS DP.ver

백준 2748, 1003, 1904. (스포를 조금 하자면 셋다 Fibonacci 관련 문제임). 1) 2748 Just Fibonacci문제. Recursion 방식으로 하면 Time Complexity에 문제가 있으니 DP방식으로 풀면 좋음. https://github.com/JangJuMan/2019-winter-PS/blob/master/...

백준 9461, 1149 -- 1) 파도반 수열 (9461): https://www.acmicpc.net/problem/9461 삼각형들의 변의 길이를 차근차근 보면 규칙을 발견할 수 있다. 이것을 이용해 점화식 세우고 문제풀면 끝 P[i] = P[i-1] + P[i-5] https://github.com/JangJuMan/2019-winter-PS/b...

백준 1932 -- 1) 정수삼각형 (백준 1932 : https://www.acmicpc.net/problem/1932) 전형적인 DP문제. 이전 길의 값을 참고하여 다음 길의 값을 정해 나가면 된다. 이전 길로 참고할 값은 각각 2개이하로 있다. 마지막 원소들 일때 참고할 값들이 1개밖에 없는 점을 유의하고 풀면 된다. 결과적으로 마지막까지 값을 ...

백준 1463, 2579 1) 백준 1463 : 1로 만들기 (https://www.acmicpc.net/problem/1463) 처음에는 소인수분해 해서 가능한 큰 수로 나누도록 하는 문제인줄 알고 있다가, 예제 생각하면서 반례를 찾아서 벙쪄있었음. 포인트가 가장 큰 수로 나눈다고 항상 가장 적은 횟수로 1을 만들 수 있는게 아니더라. (뻘짓 오짐.....

백준 10844, 2156 1) 백준 10844 (쉬운계단수 : https://www.acmicpc.net/problem/10844) 하나도 안쉬운 계단수 ㄹㅇ;;;;;; 어떻게 이런 생각을 하지;;; 아무 생각없이 앞자리 순서대로 써놓고 생각해도 생각해도 안나오는데 뒷자리를 고정시킬 생각을 하다니;; 뒷자리가 i 이면 그 다음 올 수 있는 숫자는 i-...

백준 11053, 11054 -- 1) 백준 11053 : 가장 긴 증가하는 부분수열 (https://www.acmicpc.net/problem/11053) LIS문제. 이전에 풀어봤었어서 반가웠다. 참 볼때마다 대단하다고 느끼는 문제. 구하고자 하는 것은 수열의 크기이므로 이것에 집중한다. LIS라는 벡터에 입력값들을 저장하는데 크기가 크면 이어 붙이면...