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 골목길 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 (JAVA) 7568번 덩치 - 백준(acmicpc) 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 두 사람 A 와 B의 덩치가 각각 (x,y), (p,q)라고 할 때 x>p 그리고 y>q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56,177), (45,165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 예를 들어 두 사... 자바백준Javaacmicpcbaekjoon브루트포스알고리즘Java 선물 전달 결론부터 이야기하면 N개 원소에 대한 완전순열의 수 점화식은 아래와 같다. CACHE[N] = (N - 1) * (CACHE[N-1] + CACHE[N - 2]) 점화식 유도는 아래와 같다. 수열이 아래와 같이 주어졌다고 해보자. N-2, N-1, N} 전체 경우의 수는 Case 1, Case 2의 합이 된다. Case 1) 1번 원소와 X번 원소(X in [2, N])가 서로 선물을 맞바꾼... 선물 전달acmicpcboj19471947 책 구매하기 Problem link: 전형적인 min-cost-max-flow 문제이다. source에서 person_i로 간선을 연결하는데, (source, person_i)의 capacity는 person_i가 구매를 희망하는 수량이다. bookstore_j에서 sink로 간선을 연결하는데, (bookstore_i, sink)의 capacity는 bookstore_i가 보유중인 수량이다. persio... 11405acmicpc책 구매하기boj11405 오아시스 재결합 people[1] ~ people[n]까지의 사람들이 줄을 서 있을 때, 서로 볼 수 있는 쌍의 수를 알고 있다고하자. people[n+1]이 새로 추가될 때 새로 생겨나는 쌍의 수를 구하여 더해 나가자. 새로 추가될 사람(people[n+1])이 볼 수도 있는 후보들을 유지하고, 사람이 추가될 때마다 후보들을 갱신하는 문제 후보들 중 실제로 새로 추가될 사람이 볼 수 있는 사람의 수를 헤아... 3015acmicpc오아시스 재결합boj3015 숫자 박스 일단 문제를 보고 2시간 동안 별다른 아이디어가 떠오르지 않아서 답을 보고 풀었다. 답을 보고 풀어낸 것은 차치하더라도 코너 케이스를 찾는 것에 계속 실패해서 꽤나 고전했다. CACHE[k][i][j]: k번 열까지 A[0] ~ A[i], B[0] ~ B[j]의 수를 배치할 때 곱의 최대 값 이제 CACHE[k][i][j]를 구할 때 k번째 열에 어떤 숫자가 배치될지를 생각해보면, 아래 4가... acmicpc숫자 박스1983boj1983
본대 산책 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 골목길 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 (JAVA) 7568번 덩치 - 백준(acmicpc) 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 두 사람 A 와 B의 덩치가 각각 (x,y), (p,q)라고 할 때 x>p 그리고 y>q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56,177), (45,165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 예를 들어 두 사... 자바백준Javaacmicpcbaekjoon브루트포스알고리즘Java 선물 전달 결론부터 이야기하면 N개 원소에 대한 완전순열의 수 점화식은 아래와 같다. CACHE[N] = (N - 1) * (CACHE[N-1] + CACHE[N - 2]) 점화식 유도는 아래와 같다. 수열이 아래와 같이 주어졌다고 해보자. N-2, N-1, N} 전체 경우의 수는 Case 1, Case 2의 합이 된다. Case 1) 1번 원소와 X번 원소(X in [2, N])가 서로 선물을 맞바꾼... 선물 전달acmicpcboj19471947 책 구매하기 Problem link: 전형적인 min-cost-max-flow 문제이다. source에서 person_i로 간선을 연결하는데, (source, person_i)의 capacity는 person_i가 구매를 희망하는 수량이다. bookstore_j에서 sink로 간선을 연결하는데, (bookstore_i, sink)의 capacity는 bookstore_i가 보유중인 수량이다. persio... 11405acmicpc책 구매하기boj11405 오아시스 재결합 people[1] ~ people[n]까지의 사람들이 줄을 서 있을 때, 서로 볼 수 있는 쌍의 수를 알고 있다고하자. people[n+1]이 새로 추가될 때 새로 생겨나는 쌍의 수를 구하여 더해 나가자. 새로 추가될 사람(people[n+1])이 볼 수도 있는 후보들을 유지하고, 사람이 추가될 때마다 후보들을 갱신하는 문제 후보들 중 실제로 새로 추가될 사람이 볼 수 있는 사람의 수를 헤아... 3015acmicpc오아시스 재결합boj3015 숫자 박스 일단 문제를 보고 2시간 동안 별다른 아이디어가 떠오르지 않아서 답을 보고 풀었다. 답을 보고 풀어낸 것은 차치하더라도 코너 케이스를 찾는 것에 계속 실패해서 꽤나 고전했다. CACHE[k][i][j]: k번 열까지 A[0] ~ A[i], B[0] ~ B[j]의 수를 배치할 때 곱의 최대 값 이제 CACHE[k][i][j]를 구할 때 k번째 열에 어떤 숫자가 배치될지를 생각해보면, 아래 4가... acmicpc숫자 박스1983boj1983