💻 Computer89 [1600] 말이 되고픈 원숭이 - C++ 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 1. 문제 요약 정해진 횟수에 한해서 원숭이가 말처럼 움직이며 장애물을 하나 넘어갈 수 있다, 횟수를 모두 소진하면 원숭이처럼만 움직일 수 있다. 이렇게 움직여서 맨 오른쪽 아래에 도착하는 최소한의 이동 횟수를 구하라 2. 전략 BFS를 사용하며 지금까지 이동한 횟수를 적을 이차원 배열을 사용하면 될 것 같다. 라고 생각하면 큰코다친다. 내가 그랬다. 일반적인 이차원 배열로는 해결이 안 됐는데, 그 이유가 횟수가 다 소진될 때까지 말처럼 행동하다.. 2023. 8. 23. [2146] 다리 만들기 - C++ 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 1. 문제 요약 대륙간의 놓을 수 있는 다리 중 가장 짧은 다리의 길이를 알아내야 함 2. 전략 BFS를 써야 하는 것은 너무도 당연하다. 내가 생각한 방법은 정말 간단하다, 바다옆에 육지가 있는 부분에서 모두 BFS를 돌려 보는 것이다. 그런데 위의 방법에는 한 가지 문제가 있다. 내가 출발한 대륙에서 BFS를 돌려 다른 대륙에 도착한 건지, 아니면 빙 돌아와 내가 서 있었던 대륙에 다시 도착한 건지 알 방법이 없다. 이 문제를 해결하기 위해서 나는 각 대륙마다 고.. 2023. 8. 23. [1456] 거의 소수 - C++ 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 = .. 2023. 7. 14. [2457] 공주님의 정원 - C++ 날짜를 파싱하는 방법이 정말 예술이기에 글을 쓰지 않을 수 없었다. 풀이 날짜의 간격을 구해서 풀려고 했으나, 간격과는 하등 상관 없다는 것을 답을 보고 알았다. 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;.. 2023. 7. 9. [2156] 포도주 시식 - C++ 몇 주 전에 답을 보고 풀었던 문제를 글을 쓰기 위해 다시 풀어 보았다. 어떻게 풀어야 할지는 기억이 나지 않는 상태에서 풀었다. 문제에 접근하는 방식 포도주잔에 들어있는 숫자들을 나열해 보았다. 조건이 있다면 3잔 연속으로 먹으면 안 된다는 것! (아래 사진 참고) 어떻게 해야 조건을 다 맞추며 해결할 수 있을까? 를 고민했다. $DP [1] = wine [1]$ $DP [2] = wine [1] + wine [2]$ 로 채워 줬는데, 그 이유는 어차피 2번째 와인을 맛보는 순서까지 왔을 때의 최대는 저것뿐이기 때문 이제 3번째부터가 문제의 문제의 문제인데, 뭐가 문제인지 살펴보자. 이렇게 되면 3잔 연속이 되어 버린다, 그렇기에 한 가지 방법이 있다. 1 번째 경우 이렇게 DP [i-2] 번째 잔까지.. 2023. 7. 2. [1520] 내리막 길 - C++ 문제 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 + .. 2023. 6. 30. 이전 1 2 3 4 ··· 15 다음
