acmicpc 본대 산책 2 Problme link: Adjacent Matrix로 입력을 나타내고 이를 M이라고 하자. 이때, M[i][j]는 i번 건물에서 j번 건물에 도달하는 경우의 수를 나타낸다고 하자. 이렇게하면, M^k[i][j]은 자연스럽게, k분 만에 i번 건물에서 j번 건물에 도달하는 경우의 수를 나타낸다. 거듭제곱할 행렬의 크기가 꽤 크니까, 여기서는 분할 정복 방법을 이용해주자.... bojacmicpc본대 산책 21285012850 1로 만들기 2 Problme link: 포인트 냠냠을 위한 BFS 문제이다. 숫자가 작아지면 작아지지 커질 수는 없다는 사실로부터 범위 내의 양수들만 접근하리라는 것을 알 수 있다.... boj1로 만들기 212852acmicpc12852 불 끄기 Problme link: 행 단위로 각 행에 있는 전구를 누를지 말지 결정한다고 해보자. i번쨰 행의 j번째 열에 위치하는 전구를 고려할 때, 사실 얘를 누를지 말지는 i-1행 j열의 전구가 결정한다. 문제의 특성상 만약 윗 행의 전구가 켜져 있다면 누르지 않고서는 얘를 꺼줄 방법이 없기 때문이다. 따라서, 첫 행만 전 탐색해주고 나머지 행은 그리디로 진행해주면 된다.... 14939불 끄기bojacmicpc14939 그래프 매칭 이제 C_(n+1)의 매칭 수를 헤아리는데, 아래와 같이 경우를 나누어 생각해보자. 매칭의 정의에 의해 (n, n+1), (n+1, 1)을 모두 포함할 수는 없고(n+1을 두번 포함하게 되므로), 따라서 자명하게 C_(n+1)의 매칭 수는 아래 3가지 케이스의 합이 될 것이다. Case1) (n, n+1), (n+1, 1) 모두를 포함하지 않는 매칭의 수 Case2) (n, n+1)만 포함하... acmicpc그래프 매칭3644boj3644 [DP/백준1932] 정수 삼각형 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 ... acmicpc알고리즘동적계획법acmicpc 골목길 Problem link: Bellman-Ford로 풀면 무난하게 AC를 받는 문제이다. 단, 늘상 음수사이클 문제가 그러하듯이 사이클이 있을 때 뭘 출력할지를 잘 결정해주어여 한다. 이 문제 같은 경우는 (1)사이클이 있고, (2)사이클을 시작점에서 갈 수 있으며, (3)사이클에서 도착점에 갈 수 있을 때만 -1을 출력해야한다.... acmicpc1738골목길boj1738 열혈강호 6 Problem link: 전형적인 min-cost-max-flow 문제이다. 단, 최대 비용을 구해야하므로, 비용만 음수로 처리한 후 출력시 절댓값으로 출력했다. source에서 employee_i로 간선을 연결하는데, (source, employee_i)의 capacity는 1 cost는 0 work_j에서 sink로 간선을 연결하는데, (work_j, sink)의 capacity는 1 c... 열혈강호 6acmicpc11409boj11409 이분 그래프 Problem link: 결국 이분 그래프라 함은 모든 정점 X에 대하여 모든 인접 정점 Y들이 서로 다른 집합에 들어갈 수 있음이 보장되어야 하는 것을 의미한다. 잘 생각해보면 2색을 가지고 인접한 노드끼리는 다른 색을 가지도록 그래프를 색칠하는 것과 동일하다. DFS를 진행하면서 색을 칠하는데, 모순(인접한 노드끼리 같은 색이되는 경우)이 발생할 때 중단해주면 된다.... 이분 그래프1707acmicpcboj1707 미로에 갇힌 상근 Problem link: 문제 자체는 크게 어렵지 않지만 좌표계가 6각형인 관계로 꽤나 애를 먹었다. 우상향하는 방향을 하나의 행으로 잡고, 총 29x29 크기의 배열로 생각하고 풀어주면 된다. DP를 위한 캐시정의는 아래와 같다. CACHE[turn][row][col]: turn번의 이동에 걸쳐 row, col번째 육각형에 도착하는 경우의 수 점화식은 아래와 같이 세워줄 수 있다. CACH... 미로에 갇힌 상근acmicpc5069boj5069
본대 산책 2 Problme link: Adjacent Matrix로 입력을 나타내고 이를 M이라고 하자. 이때, M[i][j]는 i번 건물에서 j번 건물에 도달하는 경우의 수를 나타낸다고 하자. 이렇게하면, M^k[i][j]은 자연스럽게, k분 만에 i번 건물에서 j번 건물에 도달하는 경우의 수를 나타낸다. 거듭제곱할 행렬의 크기가 꽤 크니까, 여기서는 분할 정복 방법을 이용해주자.... bojacmicpc본대 산책 21285012850 1로 만들기 2 Problme link: 포인트 냠냠을 위한 BFS 문제이다. 숫자가 작아지면 작아지지 커질 수는 없다는 사실로부터 범위 내의 양수들만 접근하리라는 것을 알 수 있다.... boj1로 만들기 212852acmicpc12852 불 끄기 Problme link: 행 단위로 각 행에 있는 전구를 누를지 말지 결정한다고 해보자. i번쨰 행의 j번째 열에 위치하는 전구를 고려할 때, 사실 얘를 누를지 말지는 i-1행 j열의 전구가 결정한다. 문제의 특성상 만약 윗 행의 전구가 켜져 있다면 누르지 않고서는 얘를 꺼줄 방법이 없기 때문이다. 따라서, 첫 행만 전 탐색해주고 나머지 행은 그리디로 진행해주면 된다.... 14939불 끄기bojacmicpc14939 그래프 매칭 이제 C_(n+1)의 매칭 수를 헤아리는데, 아래와 같이 경우를 나누어 생각해보자. 매칭의 정의에 의해 (n, n+1), (n+1, 1)을 모두 포함할 수는 없고(n+1을 두번 포함하게 되므로), 따라서 자명하게 C_(n+1)의 매칭 수는 아래 3가지 케이스의 합이 될 것이다. Case1) (n, n+1), (n+1, 1) 모두를 포함하지 않는 매칭의 수 Case2) (n, n+1)만 포함하... acmicpc그래프 매칭3644boj3644 [DP/백준1932] 정수 삼각형 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 ... acmicpc알고리즘동적계획법acmicpc 골목길 Problem link: Bellman-Ford로 풀면 무난하게 AC를 받는 문제이다. 단, 늘상 음수사이클 문제가 그러하듯이 사이클이 있을 때 뭘 출력할지를 잘 결정해주어여 한다. 이 문제 같은 경우는 (1)사이클이 있고, (2)사이클을 시작점에서 갈 수 있으며, (3)사이클에서 도착점에 갈 수 있을 때만 -1을 출력해야한다.... acmicpc1738골목길boj1738 열혈강호 6 Problem link: 전형적인 min-cost-max-flow 문제이다. 단, 최대 비용을 구해야하므로, 비용만 음수로 처리한 후 출력시 절댓값으로 출력했다. source에서 employee_i로 간선을 연결하는데, (source, employee_i)의 capacity는 1 cost는 0 work_j에서 sink로 간선을 연결하는데, (work_j, sink)의 capacity는 1 c... 열혈강호 6acmicpc11409boj11409 이분 그래프 Problem link: 결국 이분 그래프라 함은 모든 정점 X에 대하여 모든 인접 정점 Y들이 서로 다른 집합에 들어갈 수 있음이 보장되어야 하는 것을 의미한다. 잘 생각해보면 2색을 가지고 인접한 노드끼리는 다른 색을 가지도록 그래프를 색칠하는 것과 동일하다. DFS를 진행하면서 색을 칠하는데, 모순(인접한 노드끼리 같은 색이되는 경우)이 발생할 때 중단해주면 된다.... 이분 그래프1707acmicpcboj1707 미로에 갇힌 상근 Problem link: 문제 자체는 크게 어렵지 않지만 좌표계가 6각형인 관계로 꽤나 애를 먹었다. 우상향하는 방향을 하나의 행으로 잡고, 총 29x29 크기의 배열로 생각하고 풀어주면 된다. DP를 위한 캐시정의는 아래와 같다. CACHE[turn][row][col]: turn번의 이동에 걸쳐 row, col번째 육각형에 도착하는 경우의 수 점화식은 아래와 같이 세워줄 수 있다. CACH... 미로에 갇힌 상근acmicpc5069boj5069