Ctstudy4

layout: single title: “[BOJ]DP 50제” categories: boj toc: true toc_sticky: true

Coding Test Study 4

💻230401~230407 (브2~실4)

1. 피보나치수5 (브2) 10870

런타임 에러 주의 : F = [0]*(n+1)이면 0을 입력했을 때 F[1] = 1에서 배열을 벗어나게 된다.

2. 피보나치수2 (브1) 2748

3. 다리놓기(실5) 1010

팩토리알 값을 다 dp 테이블에 저장하면 됨

4. 돌게임 (실5) 9655

1개 또는 3개를 가져갈 수 있음

따라서 N이 홀수일때

상근이가 가져가면 무조건 짝수가 되고 창영이가 가져가면 무조건 홀수가 됨

5. 설탕 배달 (실4) 2839

런타임 에러 주의 : dp = [-1]*(N+1)이면 0을 입력했을 때 dp[3] = 1에서 배열을 벗어나게 된다.

💻230408~230414 (실3~실3)

6. Four Squares (실3) 17626

처음에 아예 50001 길이의 배열 만들기

n보다 작은 제곱수 중 가장 큰 수에서 갱신하는 게 아님

'n-제곱수'를 다 돌려보면서 최솟값 찾고 거기서 갱신해야 함

예시

n = 23일 때, j*j는 1, 4, 9, 16 이고

dp[23-1], dp[23-4], dp[23-9], dp[23-16] 중 가장 작은 값에서 +1을 한 것이 dp[23]임

7. 1로 만들기 (실3) 1463

1로 만드는 것이기 떄문에 dp[1]은 0임

1을 더한 것, 2로 나눈 것, 3으로 나눈 것 중 가장 작은 수에 1을 더하면 됨

8. 1,2,3 더하기 (실3) 9095

1, 2, 3의 합으로 나타내는 것은 dp[1], dp[2], dp[3]까지 구해야함

dp[4] = dp[1]+dp[2]+dp[3]

9. 2xn 타일링 (실3) 11726

1, 2의 합으로 나타내는 것과 동일

dp[1], dp[2] 까지가 초깃값

dp[3] = dp[1]+dp[2]

10. 계단 오르기 (실3) 2579

1. dp[i][0]: 바로 전 값을 안 더하는 값

dp[i-1]은 고려하지 않고

dp[i-2][0]과 dp[i-2][1] 중 큰 수에 현재 값을 더하면 됨

2. dp[i][1]: 바로 전 값을 더하는 값

dp[i-1][0]은 바로 전 값을 안 더한 값

따라서 여기에 현재 값을 더하면 됨

dp[i][0]과 dp[i][1] 중 큰 값 출력

💻230415~230421 (실3~실2)

11. 2xn 타일링2 (실3) 11727

12. 조합 (실3) 2407

13. 가장 긴 증가하는 부분수열 (실2) 11053

0부터 i까지 돌면서

dp[본인보다 작은 값]+1 로 최댓값 갱신

dp[본인과 같은 값] 으로 최댓값 갱신

현재값은 이전에 나온 같은 값보다 무조건 크거나 같을 수 밖에 없기 때문에 dp이다.

14. 연속합 (실2) 1912

dp[i][0]은 현재값을 추가하는 경우

이전 값에 현재값 추가 vs 그냥 현재값

이전 값이 음수라면 그냥 현재값이 더 큰 수이다.

dp[i][1]은 현재 값을 추가하지 않은 경우

이전 두개의 값 중 큰 수로 갱신

💻2024~~2025 (살2)

15. 가장 큰 증가하는 부분수열(실2) 11055

16. 가장 긴 짝수 연속한 부분수열 small (실2) 22857

17. 스티커 (실1) 9465

2개열 왼쪽의 위아래 두 개와

1개열 왼쪽 두 개 중 현재값과 행이 다른 것

총 세 개 중에 가장 큰 값에 현재 값을 더한 것이 가장 큰 값이다.

19. 포도주 시식 (실1) 2156

20. 쉬운 계단 수 (실1) 10844

21. 구간 합 구하기 5 (실1) 11660

22. 징검다리 건너기 (실1) 21317

23. 징검다리 건너기 small (실1) 22869

24. 퇴사2 (골5) 15486

25. 호텔 (골5) 1106

26. 동전1 (골5) 2293

27. 동전2 (골5) 2294

28. 파스칼 삼각형 (실4) 15489

29. 연속부분최대곱 (실4) 2670

30. 점화식 (실4) 13699

31. Maximum Subarray (실4) 10211

32. 피보나치수7 (실4) 15624

33. 수열 (실4) 2491

34. 퇴사 (실3) 14501

35. 피보나치 함수 (실3) 1003

36. 이친수 (실3) 2193

37. 파도반 수열 (실3) 9461

38. 피보나치는 지겨웡~ (실3) 17175

39. 달나라 토끼를 위한 구매대금 지불 도우미 (실3) 17212

40. 제곱수의 합 (실2) 1699

41. 1,2,3 더하기 5 (실2) 15990

42. 그래픽스 퀴즈 (실2) 2876

43. Game Addiction (실2) 20152

44. 가장 긴 감소하는 부분 수열 (실2) 11722

45. 상자넣기 (실2) 1965

46. 점프 점프 (실2) 11060

47. 1,2,3 더하기 3 (실2) 15988

48. 자원 캐기 (실2) 14430

49. 병사 배치하기 (실2) 18353

50. 새끼치기 (실2) 17291