몇 주 전에 답을 보고 풀었던 문제를 글을 쓰기 위해 다시 풀어 보았다. 어떻게 풀어야 할지는 기억이 나지 않는 상태에서 풀었다. 문제에 접근하는 방식 포도주잔에 들어있는 숫자들을 나열해 보았다. 조건이 있다면 3잔 연속으로 먹으면 안 된다는 것! (아래 사진 참고) 어떻게 해야 조건을 다 맞추며 해결할 수 있을까? 를 고민했다. $DP [1] = wine [1]$ $DP [2] = wine [1] + wine [2]$ 로 채워 줬는데, 그 이유는 어차피 2번째 와인을 맛보는 순서까지 왔을 때의 최대는 저것뿐이기 때문 이제 3번째부터가 문제의 문제의 문제인데, 뭐가 문제인지 살펴보자. 이렇게 되면 3잔 연속이 되어 버린다, 그렇기에 한 가지 방법이 있다. 1 번째 경우 이렇게 DP [i-2] 번째 잔까지..

문제 DFS를 사용하여 이미 지나간 흔적이 있는 경로는 계산하지 않는 방법으로 구현해야 한다. 그렇기에 DP도 사용하여 흔적을 만들어야 함을 알 수 있다. DP[i][j] = [i, j] 지점에서 부터 도착지점까지 갈 수 있는 경우의 수 입력을 받을 때 DP를 -1로 초기화해준다, -1은 아직 방문하지 않았다는 뜻이다. 이 문제를 풀며 놀랐던 부분이 있다면, DFS를 사용하는데 Stack을 사용하지 않고 바로바로 호출하는 것이었다. int dfs(int x, int y){ if(dp[x][y] != -1)return dp[x][y]; if(x == n-1 && y == m-1) return 1; dp[x][y] = 0; for(int dir = 0; dir < 4; ++dir){ int nx = x + ..

2시간 정도 고민하며 여러 가지 아이디어들을 구현해 보도 결국에는 답을 보았다. 문제 1. N이 홀수 라면 타일을 채울 수 없다는 것을 알아냈다. 꾸역꾸역 채워 넣어도 한 칸이 남는 것을 알 수 있다. 2. $3\times 2$ 타일의 경우의 수 밑에 그림처럼 3가지 가능하다 N이 4일 때부터 DP를 채워 주면 될 듯싶다. 3. $3 \times 4$일 때 $$ 3 \times 3 = 9$$ 또 특수케이스를 고려해 줘야 하는데 아래처럼 2가지가 있다 직접 그려보면 알겠지만, 각 숫자에 존재하는 특수케이스는 두 개뿐이며 위 두 개 이외는 모두 중복이 됨을 알 수 있다 총 $9 + 2 = 11$가지 4. $3 \times 6$일 때 $$11 \times 3 = 33$$ 여기서부터 중복이 발생하게 되는데, 어..

온전히 내 힘으로 풀었다 할 수는 없지만, 첫 플레티넘 문제이고 내가 생각한 아이디어와 다른 사람의 아이디어를 적어보고 싶어 글로 작성해 본다. 아이디어 일단 규칙(?)을 찾아보려고 한다. 전 값보다 큰 게 들어온다면 전 값(2) 보다 큰 값이 들어온다면 앞의 2는 다음 사람을 보지 못하기 때문에 스택에 존재할 이유가 없어진다. 4와 같거나 큰 값, 또는 스택이 빌 때까지 POP해 준다. 전 값보다 작은 값이 들어온다면 카운트를 증가시킨다 같은 값이 들어온다면 그렇다 (2, 2), (2, 2), (2, 2), (4, 2), (4, 2), (4, 2)가 가능하다. 중복된 값을 생략하여 넣는 방법을 스택을 하나 더 만들어 구현해 봤지만 아닌 것 같아 중간에 그만뒀다. 이 부분을 대체 어떤 식으로 구현해야 할..

풀이 이번 글에서는 어떻게 구상하고 설계했는지 자세하게 적어 보려고 한다 1. 나에게 가까운 것을 찾아야 한다. BFS를 사용할 수 있을 듯하다. 가까운 것이 여러 개 있다면 가장 위에 있는 것, 그중에서도 여러 개 있다면 가장 왼쪽의 것을 고르라 하니 BFS를 돌고 for문을 사용해도 될 듯하다. 시간을 표시해줘야 하니 Dist라는 -1로 채워진 $ N \times N $ 배열을 만들어 줘야 한다. 2. 상어를 성장시켜야 한다. baby라는 상어의 현재 크기를 담는 변수 growing이라는초기값은 0이고, 물고기를 먹을 때마다 증가시킨다. 만약 baby 변수와 값이 동일해진다면 baby증가, growing은 0으로 초기화 즉 상어의 무게를 늘려주는 식으로 구상했다. 3. 종료 조건 무한 반복을 돌리며 ..

문제 모든 경우의 수를 확인하는 브루트 포스로 푸는 것은 불가능해 보인다. N은 최대 2000개 이고, 질문의 개수가 최대 1,000,000개 [ 1, 2000 ]이라는 질문이 1,000,000개 나온다면 20억 번 연산을 해야 하므로 0.5초 안에는 절대 불가능 Q. DP로는 가능 할까? A. 가능하다. 점화식 명령 : [ 1, 7 ]이 팰린드롬이지 확인하고 싶다면 [ 2, 6 ] 이 팰린드롬 인지 확인 하고 [ 1 ] == [ 7 ]이 같은 지 확인해 주면 된다. 그런데 또 [ 2, 6 ]이 팰린드롬인지 알려면 [ 3, 5 ]를 알아야 하므로 DP로 풀 수 있다. 테이블 정의 DP [ i ][ j ] = i번째부터 j번째 까지가 팰린드롬 인지 확인 Boolean Type 입력받기 for(int i =..

문제 왜 DP를 써야 하는지 감조차 오지 않을 당신을 난 이미 알고 있다. 기본 적으로 입력이 1일 때는 10개이다. 0 1 2 3 4 5 6 7 8 9 2일 때 00 01... 09 - 10개 11 12... 19 - 9개 22 23... 29 - 8개 33 34... 39 - 7개 ... 99 - 1개 3일 때 000 001... 009 - 10개 011 012... 019 - 9개 022 023... 029 - 8개 ... 999 뭔가가 보인다면 대단한 것이며, 안 보여도 좋다, 당신의 눈을 뜨이게 하는 것이 나의 역할이다. Q. DP 테이블에 어떻게 의미를 부여해 줘야 할까? A. DP [i] = i번째 숫자가 처음인 상태에서의 최대 경우의 수 위의 설명은 좀 어려울 수 있으니 그림으로 보자 그림..

이 글은 정말 이해가 가지 않는 분들을 위해 쓰인 글입니다. 문제 브루트 포스를 생각할 수 도 있지만 $ O(2^n) $이며 입력의 최대 값이 100'000만 인 것을 보아 불가능하다. Q. 과연 DP로는 풀 수 있을까? A. DP [i] = i번째 까지 스티커를 떼었을 때의 최댓값으로 놓고 푼다면 가능하다. 경우의 수들이 존재하는데 그림으로 보자 i번째 스티커를 떼기 위한 경우의 수들 떼려는 스티커 = 파란색 파란색을 뗴기 위한 전까지의 최댓값 = 주황색 위 그림처럼 4가지 존재하며 이것을 구현해 주면 된다. 코드 #include using namespace std; void init(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } in..

정말 너무 진이 빠진다ㅏㅏ 풀이 정사각형인지 판단하려면 어떻게 해야 할까? 위, 옆, 대각선을 확인하면 된다. 이걸로 이 문제는 해결이라 볼 수 있다. 점화식 $$\large dp [x][y] = min(\{dp [x-1][y], dp [x][y-1], dp [x-1][y-1]\})$$ 전체 코드 #include using namespace std; void init(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } int n, m; int arr[1002][1002], dp[1002][1002]; int main(){ init(); cin >> n >> m; //입력 for(int i = 1; i > str; for(int j = 1; j

풀이 먼저 내가 썼던 글을 보고 오도록 하자, 그래야 이 문제도 이해할 수 있다! https://juuuuung.tistory.com/126 [9251]LCS - C++ 풀이 LCS - 최장 공통부분 수열 점화식 if(A[i-1] == B[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]); 비교하는 두 문자가 같다면 dp [i-1][j-1] + 1 비교하는 두 문자가 다르다면 dp[i-1][j], dp [ juuuuung.tistory.com ※위의 글을 읽었다는 가정하에 풀이를 시작하겠다.※ 최대 공통 문자열의 수를 구하는 알고리즘(LCS) cin >> A >> B; for(int i = 1; i A >> B; ..