반응형 [백준]214 [BaekJoon/백준] 1890번 점프 경로의 개수는 2^63-1보다 작거나 같다. 경로 DP값은 int로는 못 담는다. dfs bfs 같은 탐색으론 불가능하다. Dynamic Programming (동적 계획법)을 이용해야 한다. 나 근데 DP 왜이렇게 못해졌지 ㅜ.ㅜ 한시간 붙잡고 못 풀어서 해설을 찾고 도움을 받았다. DP 풀이 방법에는 본래 두 가지가 있는데 1. 재귀 + 메모이제이션 = Top down 2. 반복문 + 타뷸레이션 = Bottom up 두 가지 다 이용해 볼 것이다. 각 방법에서 DP[i][j]의 의미는 이러하다. 1. 메모이제이션 : 해당 위치에서 목적지까지 가는 경로 수 2. 타뷸레이션 : 해당 위치까지 가는 경로 수 메모이제이션 메모이제이션 문제를 풀 때, DP에 값이 들어있는지 여부를 따져서, 들어있으면 재귀하지.. 2022. 7. 4. [BaekJoon/백준] 1331번 나이트 투어 나는 문제에서 요하는 대로, 정석적이게 풀어서 다른 분들의 코드보다 다소 복잡할 것 같다고 생각했는데 내 코드가 잘 짠 코드인 것 같다..! 그리고 이 문제에 도움이 필요한 분들도 풀이가 잘 이해가 되실 수 있을 것 같다. 체크포인트는 두 가지. 경로가 겹치는가 각 경로가 닿을 수 있는 거리인가 ( 두 경로 A3 B1가 있을 때, (|A - B| == 1 && |3 - 2| == 2) 또는 (|A - B| == 2 && |3 - 1|) == 1 여야 닿을 수 있다) 체크포인트 1은, 단순히 입력 안에 겹치는 문자가 있을 때로 발견할 수 있다. 차례로 입력을 받으면서 하나의 문자열로 계속 합쳐서 붙여나가고, 이 내에서 중복된 입력이 있으면 해당된다. 체크포인트 2는, 이렇게 하나의 문자열로 만든 곳을 분할.. 2022. 7. 3. [BaekJoon/백준] 13458번 시험 감독 브론즈 티어의 문제인데 왜 정답률이 27%라는 것은.. 생각하기 쉽지 않은 반례가 있다는 건데 나 역시나 그 덫에 걸렸다. 두 가지가 있는데, 일단 나는 개인적으로 문제에 수정을 요청드리고 싶다(이미 요청드린 분들이 있는데, 수정이 안되었다) 총 감독관은 각 방마다 무조건 한 명 있어야 한다. (https://www.acmicpc.net/board/view/81575) 나도 없어도 되는 거로 이해했는데, 있어야 했다. 그리고 나머지 한 가지는, 그냥 신경쓰지 못한 부분이다. 입력이 최악의 경우일 때, 총 감독관 수가 int 범위를 넘어갈 수 있음을 주의해야 한다. (https://www.acmicpc.net/board/view/61603) #include #include using namespace st.. 2022. 7. 3. [BaekJoon/백준] 14501번 퇴사2 퇴사 1번 문제(https://hevton.tistory.com/586)는 완전탐색으로 풀었다고 봐야 한다. O(N^2)의 알고리즘이니까,, 150만 x 150만은 퇴사2에서 시간초과가 나올 수 밖에 없다. DP를 사용해야 한다. 근데 나 DP 왤케 못하지??? 이 문제 두시간 붙잡고 못풀어서 해설 찾아봤다. 근데 문제 해설도 이해가 잘 안된다. 해설만 두시간 더 붙잡았다. 나 오늘 진짜 코테 망하더니 멘탈 나갔나보다. 진짜 화가 많이 나긴 했다.. 인터넷 진짜 다들 하향식으로만 풀던데, 이유는 왤까.. 상향식은 아예 불가능한 것인가.. 의문이 들어서 막 찾아봤는데 별다른 해설이 없었다. 일단 지금은 못해보겠다. 정말 피곤해 죽겠고 아무것도 안잡힌다. 5시간을 붙잡았는데도 안되는거면, 오늘은 쉬어야겠지... 2022. 7. 3. 이전 1 ··· 10 11 12 13 14 15 16 ··· 54 다음 반응형
