128651 [C] 12865: 평범한 배낭 Knapsack Problem은 학교 알고리즘 시간에 배웠어서 어떻게 해야하는지는 알고 있었는데.. 푸는데 한시간 넘게 풀었다. 그에 대한 교훈이 뭐였냐..! 첫째, 웬만해서 전역변수로 배열을 초기화하자.. 배열의 범위만 넘어가지 않는 선에서 (약 2억) 가장 쉽고 따로 초기화 해주지 않아도 되된다. 둘째, 배열의 인덱스를 정할때 0부터 시작할지 혹은 1부터 시작할지를 확실히 정하고 시작하자. 셋째, 이차원배열도 효과적이지만 그냥 배열 2개를 따로 정하는게 헷갈리지 않는 경우가 있다. 이 문제도 점화식을 구하고, for문을 이용해서 작은문제들을 풀어 결국 결과까지 도출해내는 Bottom-Up방식을 사용했다. 밑에는 소스코드다.. #include int backpack[2][102]; int dp[102].. 2023. 7. 22. 이전 1 다음