fatalite

문제 문제 난이도 : 프로그래머스 4단계 문제 분류 : 다이나믹 프로그래밍 문제 리뷰 환형이라서 헛짓거리 하다가... 1시간 20분 만에 아이디어 떠올리고 호다닥 풀었다... 그래도 조금은 성장했나보다 ㅠ 문제 소스 코드 #include #include #include using namespace std; int solution(vector money) { int answer = 0; int n = money.size(); int DP1[1000001]; int DP2[1000001]; // DP[1] = 1 // DP[2] = 2 // DP[3] = 3 // DP[4] = 4 // DP[5] = 8 // 1 2 3 1 5 // 1 2 3 1 // 2 3 1 5 DP1[0] = 0; DP2[0] = 0;..

문제 문제 난이도 : 프로그래머스 4단계 문제 분류 : 다이나믹 프로그래밍 문제 리뷰 내가 이게 DP 문제라는 걸 몰랐다면 풀 수 있었을까..? 그리고 처음에는 DP[i][j] 이런 식으로 둬서 덧붙일때 + 만 고려되었다. 테스트 케이스는 맞길래 뭐지 했는데, - 일 경우에는 - (최소값)으로 해야지 최대값으로 갱신할 수 있다. 물론 질문하기에 자세하게 해설해 놓은게 있지만, 기억용으로... 문제 소스코드 #include #include #include #include using namespace std; int solution(vector arr) { int answer = -1; vector IntArr; vector OperArr; IntArr.push_back(-1); OperArr.push_ba..

문제 문제 난이도 : 3단계 문제 분류 : 다이나믹 프로그래밍 문제 리뷰 저번에 풀어본 문제와 비슷하고 그것보다 쉬워서 금방 풀었다. 만약 BFS 같은 탐색을 사용하였다면, 조합이 폭발적으로 상승해서 시간 초과나 메모리 초과가 뜨지 않았을까 싶다. 초등학교 때 배웠던 경우의 수 개념을 사용하면 좋은 문제이다. Base Case로 DP[1][2 ~ N]과 DP[2 ~ N][1]를 처리해준다. 한 가지 밖에 없거나, 가는 길에 개울이 있다면 0이 된다. DP[i][j]는 j,i로 가는 경우의 수를 저장한다. DP[i][j]로 오는 방법은 DP[i-1][j] + DP[i][j-1] 이므로 이를 사용하면 되고, 만약 개울이 있다면 0으로 처리한다. 문제 소스코드 #include #include #include ..