슈뢰딩거의 고등어

https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr [풀이방법] 이 문제는 n, m 이 y, x 이다. 위치가 바뀌어져있어서 헷갈릴 수 삽질을 할 수가 있다. 최단 거리가 조건인데 이동가능한 방향이 오른쪽/아래쪽 두가지 방향으로밖에 이동할 수 없기 때문에 항상 x, y 에 있을 때 최단거리로만 이동할 수 밖에 없다. 따라서, 그냥 n, m 으로 이동 가능한 모든 경우의 갯수를 구하면 된다. dp 식은 ..

https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 처음에 보고 익숙하긴 했는데, 이런 문제는 DFS 로 풀었던지라 왜 DP 로 풀란건지 싶었다. 얼추 숫자 횟수를 기준으로 잡으면 되겠다라고 생각했다. 1. DP 에 N 사용횟수를 인덱스로 잡고 2. 만들 수 있는 숫자들을 집어 넣는다. - x개를 사용해서 만들수 잇는 수를 구하는 방법은 1) NNNN....NN : x번 그냥 숫자만 이용 2) k는 1~k-1 까지 - dp[x-k] + dp[k] - dp[x-k] * dp[k] - dp[x-k] - dp[k] - dp[x-k] / dp[k] - 주의해야 할점은 나누기 할때 수를 0 으로 나누..

https://programmers.co.kr/learn/courses/30/lessons/1837 코딩테스트 연습 - GPS edge_list [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4], [3, 5], [4, 6], [5, 6], [5, 7], [6, 7]] programmers.co.kr [풀이방법] DP 로 풀어보자 DP[i][j] -> i 시간에 j 로 가려면, 얼마나 수정되어야 하는지 최소의 수 DP[마지막시간][마지막점] 을 answer 로 리턴해주면 된다. 1. gps_log 를 기반으로 dp 를 초기화 해준다. INF 로 다들 초기화해주고, DP[0][시작점] = 0; // 0시간에 시작점 변경은 안해도 되니까 고정이니까 2. i 시간에 j 위치에 올 수 있는 ..

https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net dp 는 메모이제이션이 핵심이다. 특정 값이 들어갔을때마다 계산을 해주는 것이 아니라 이전에 계산했던 결과를 저장해놓고 그 값을 사용하는 것이 핵심! 이 문제에서는 인자가 3개이므로, 삼차원 배열로 각 인자들을 저장을 해주자. [풀이] 1. 매번 호출할때마다, 그 결과값을 dp 배열에 저장해준다. 2. 함수를 호출했을때, 그 전에 그 함수로 호출한 적이 있다면 (dp[a][b][c] != 0) 이라면..

https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net [풀이] 쭉 경우의 수를 적어보다보니 규칙이 보였다. DP[i] = min(DP[i-5] + 1, DP[i-2] + 1) DP[2] = 1, DP[5] = 1, DP[4] = 2 계산을 할 수 없는 경우들이 존재하는데 우리는 min 함수를 사용하기 때문에 계산을 할 수 없는 경우를 고려하려면 초기에 DP 함수를 987654321 로 초기화를 해주어서 계산이 가능한지 아닌지 판별하면 된다. 사실 1~100000 의 수에서 거슬름돈을 줄 수 없는 경우는 1과 3뿐이다. 하지만 위의 공식으로 돌리다보면 1, 3 을 큰 수..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 초반 생각한 방식은 m개중 n 개를 뽑으면 자동으로 된다고 생각했다. 그래서 익숙한 dfs로 길이가 n인 조합을 구했는데 시간초과가 떳다...ㅎ 경우의 수만 구하면 되는 거니까 수학공식을 사용해서 하면 될것이라고 생각해서 했지만 결과값이 int 가 담을 수 없는 숫자라서 실패 그래서 타입을 long long 에서 unsigned long long 으로 변경한 후 해봤지만 시간초과... and 50..

https://www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 난 정말 DP 가 약하다... 코테에서 나오는 DP 가 다 거기서 거기라고는 하지만 많이 안풀어봐서 방법자체를 잘 못 찾는다. 계속 풀다보면 되겠지 싶은 마음으로 브론즈부터 풀어보았다. [ 풀이 ] 1. 각 스텝마다 a, b 의 갯수를 저장할 자료구조를 정의한다. pair DP[50]; 2. 초기는 A 하나이므로 DP[0] = {1, 0} 이다. 3. 그 다음 식을 구하자 idx a의 갯수 b의 갯수..