1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 1. 문제 요약 정해진 횟수에 한해서 원숭이가 말처럼 움직이며 장애물을 하나 넘어갈 수 있다, 횟수를 모두 소진하면 원숭이처럼만 움직일 수 있다. 이렇게 움직여서 맨 오른쪽 아래에 도착하는 최소한의 이동 횟수를 구하라 2. 전략 BFS를 사용하며 지금까지 이동한 횟수를 적을 이차원 배열을 사용하면 될 것 같다. 라고 생각하면 큰코다친다. 내가 그랬다. 일반적인 이차원 배열로는 해결이 안 됐는데, 그 이유가 횟수가 다 소진될 때까지 말처럼 행동하다..

2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 1. 문제 요약 대륙간의 놓을 수 있는 다리 중 가장 짧은 다리의 길이를 알아내야 함 2. 전략 BFS를 써야 하는 것은 너무도 당연하다. 내가 생각한 방법은 정말 간단하다, 바다옆에 육지가 있는 부분에서 모두 BFS를 돌려 보는 것이다. 그런데 위의 방법에는 한 가지 문제가 있다. 내가 출발한 대륙에서 BFS를 돌려 다른 대륙에 도착한 건지, 아니면 빙 돌아와 내가 서 있었던 대륙에 다시 도착한 건지 알 방법이 없다. 이 문제를 해결하기 위해서 나는 각 대륙마다 고..

1. 문제의 추상화 A ~ B (A, B포함) 사이의 수 중에서 거의 소수를 구한다. 거의 소수란 소수를 N제곱한 수를 말한다. 예를 들면 $5^2 = 25$, $5^3 = 125$, $7^2 = 49$ 등이 문제에서 말하는 "거의 소수"이다. 2. 문제 계획 에라토스테네스의 체를 사용하여 소수들을 찾아낸다. 소수들의 집합을 순회하며 "거의 소수"를 찾아낸다. 위처럼 크게 두 가지로 나눌 수 있다. 3. 주의해야 할 점 $10^{14}$은 100조이다. 여기서 우리는 INTOVERFLOW를 조심해야 함을 알 수 있다. 4. 에라토스 테네스 const int Max = 10'000'000; //10^7 : 1000만 vector arr(Max+1, 1); void decimal(){ for(int i = ..

날짜를 파싱하는 방법이 정말 예술이기에 글을 쓰지 않을 수 없었다. 풀이 날짜의 간격을 구해서 풀려고 했으나, 간격과는 하등 상관 없다는 것을 답을 보고 알았다. for(int i= 0; i > m1 >> d1 >> m2 >> d2; v.push_back({m1*100+d1, m2*100+d2}); } //3월 1일 = 301 //5월 28일 = 528 위와 같이 날짜를 파싱한다. 3월 1일 부터 11월 30일 까지만 꽃이 연속하여 피어 있기만 하면 된다고 한다. 계속 계속 비교해가며 가장 최소를 구해준다. 말로 설명하기 어려우니 코드로 보자 int ans = 0; int t = 301; while(t < 1201){ int nxt = t;..

몇 주 전에 답을 보고 풀었던 문제를 글을 쓰기 위해 다시 풀어 보았다. 어떻게 풀어야 할지는 기억이 나지 않는 상태에서 풀었다. 문제에 접근하는 방식 포도주잔에 들어있는 숫자들을 나열해 보았다. 조건이 있다면 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 =..