출처 : https://www.acmicpc.net/problem/1613 "플로이드와샬!" 사건의 전후 관계에 대해 묻고 있다. 플로이드와샬은 음수 가중치를 계산할 수 있다는 점이 다익스트라와 다르다. 문제에서 친절히 -1,0,1 과 같이 힌트를 주었다. 주어지는 사건 x,y 에 대해 1 과 -1 을 부여한다. x y 순으로 주어진다면 아래와 같다. map[x][y] = 1 ;map[y][x] = -1; 그렇 다면 x y 두 사건의 관계를 x < y 라고 하자. 이렇게 되면 이제 우리가 찾아야 할 것은 x < (...) < y 의 관계를 만족하는 다른 사건들과의 관계 이다.이를 아래와 같이 계산한다. 가장 바깥쪽 for문이 우리가 찾을 (...) 에 해당한다. for (int a = 1; a j 라면,..
출처 : https://www.acmicpc.net/problem/5566 "단순 시뮬레이션" 123456789101112131415161718192021222324252627282930313233343536373839import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { static int N,M; static int[] map; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader..
백준 3048. 개미 (https://www.acmicpc.net/problem/3048) "단순 시뮬레이션" 해당 문제는 단순 시뮬레이션 문제인 것 같다. 실제로 해보는 것이 답. 근데 어떻게 구현 할 것인가. 단순 시뮬레이션을 돌려야 하는 것인가? 어떤 수식 수식이나 그리디하게 풀 수 있는 방법이 있나? 잘 모르겠다. 무식하게 다 해보자. 나는 구현에 ArrayList 를 사용했다. 두 그룹을 ArrayList에 넣고 반대 방향의 개미를 만나면 위치를 서로 바꿔주었다. 그리고 실제 개미들이 모두 지나갔는데도 T 값이 증가할 것을 염려하여 시뮬레이션 이전에 T 값을 비교하여, 모두 지나간 시간보다 더 큰 T값이 주어지면 그냥 문자열을 붙여서 출력하고 끝냈다. 아 그리고 매번 System.out.prin..
출처 : 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