백준 3048. 개미 (https://www.acmicpc.net/problem/3048) "단순 시뮬레이션" 해당 문제는 단순 시뮬레이션 문제인 것 같다. 실제로 해보는 것이 답. 근데 어떻게 구현 할 것인가. 단순 시뮬레이션을 돌려야 하는 것인가? 어떤 수식 수식이나 그리디하게 풀 수 있는 방법이 있나? 잘 모르겠다. 무식하게 다 해보자. 나는 구현에 ArrayList 를 사용했다. 두 그룹을 ArrayList에 넣고 반대 방향의 개미를 만나면 위치를 서로 바꿔주었다. 그리고 실제 개미들이 모두 지나갔는데도 T 값이 증가할 것을 염려하여 시뮬레이션 이전에 T 값을 비교하여, 모두 지나간 시간보다 더 큰 T값이 주어지면 그냥 문자열을 붙여서 출력하고 끝냈다. 아 그리고 매번 System.out.prin..
출처 : https://www.acmicpc.net/problem/2186 "전형적인 DP 문제, 재귀 호출 및 리턴에 대해 잘 알고있자." N,M 의 범위를 고려하면 100,000 개의 칸이 존재한다. 대략 계산해 봤을 때, 100*100 개 칸에서 갈 수 있는 방법의 개수는 4가지 방향에 최대 5칸의 거리 20개가 된다. 20^100,000 ... 브루트 포스로는 절대 돌아가지 않는다. 100 * 100 격자에 모든 문자가 'B' 이며 'BB' 를 만드는 경우의 수를 생각해보면 굉장히 많다. 그리디한 방법도 없고, 이럴 때는 DP 를 이용해 푸는 것이 좋겠다. 사실 이런 격자 문제를 풀때 DP를 사용하면 나는 항상 DP[X][Y][?] 이런 식으로 놓고 생각해본다. 무엇을 어떻게 메모이제이션 할 것인..
출처 : https://www.acmicpc.net/problem/12761 "DP를 사용할 때, 부등호를 조심하자." 해당 문제를 BFS를 이용해 풀었다. 대충 계산해보아도 총 100,001 개의 지점이 있고, 각 지점마다 갈 수 있는 경우의 수는 8 가지 이므로 8^100000 이나 되므로(실제로는 이보다 작겠지만) 그냥 단순 탐색으로는 무리가 있고, 메모이제이션을 이용해서 가지치기를 해줘야 했다. 지점 A에서 B로 간다고 했을 때, 내가 지점 B까지 가는데 걸린 횟수를 저장하는 것, 단 이때 DP[B] 에 값이 INF 가 아니라면(이미 누군가 방문 했다면) 나보다 지점 A를 더 짧은 횟수 안에 통과했는지를 비교한다. if ( dp[B]
- Total
- Today
- Yesterday