sncap Style

www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net dfs로 풀수 있지만. 위상정렬 공식으로 풀었다. 훕냐.. 공식.. 은 공식이다. import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.ut..

www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 위상정렬 공부다가.. 결국 DP로 처리한다.. 위상정렬이 어렵네.. import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; p..

www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net dfs 문제인 줄 알았는데.. DP 문제다. 잘 모르겠어서 이삭님 풀이 보고 풀었다. blog.naver.com/kdy246/222184773335 백준 알고리즘 - #2225 합분해 문제/생각 정리 문제문제 풀이한 방법이 문제는 다이나믹 프로그래밍을 활용하면 쉽게 풀 수 있었다.​생각해봐야 할 것은 ... blog.naver.com 파스칼의 삼각형 문제로 D[i-1][j] + D[i][j-1]을 반복해서 계산하는 형태이다. 그런데.. 왜 D[N][K] 가 답이 아닌 D[N][K-1] 이 답이 되는지는 모르겠다.. 움움 어렵네

www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 위상정렬을 이용한 문제인데.. 문제 자체 이해가 어렵다. 최단거리가 아닌, 최장 거리를 구하고.. 그때 간선의 개수를 구하는 문제이다. DP 스럽게 풀었다. import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; imp..

https://www.acmicpc.net/problem/2820 2820번: 자동차 공장 상근이는 자동차를 매우 좋아한다. 자동차 공장에 취직한 상근이는 계속된 승진 끝에 드디어 사장이 되었다. 공장에는 총 N명의 직원이 있다. 상근이를 제외한 모든 직원은 한 명의 상사가 있다. www.acmicpc.net 우선 문제 이해가 어려웠다. 뭘 하라는건지... 한참 만에 따라 하다 억지로 이해중.. 우선 range update를 팬윅트리를 이용해서 진행했다. static void updateRange(int a, int b, int v){ update(a, v); update(b+1, -v); } 문제는 하위 직원을 구하는 부분이 었는데.. 단순 dfs의 탐색이 아니라. 전위순회(pre-order)를 찾아야..

www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 부분합이지만, 부분합의 원소를 구하는 것이 아니라, 부분합이 S인 최소원소 길이를 구하는 것이라, 투포인트 S, E로 구하면 된다. 처음엔 접근이 어려웠으나,.. 풀다 보니.. 조금씩 이해하려 한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.S..

www.acmicpc.net/problem/15653 15653번: 구슬 탈출 4 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 많이 어렵다... 훕냐.. 손으로 해보는게 더 쉬운듯 했다. 문제는 그냥... 그냥 반복해서 풀면 된다.. BFS 문제.. import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import ja..

www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 어렵게 생각했는데.. 위상정렬 최대 값으로 해결함. DP import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public clas..

https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 문제 위대한 해커 창영이는 모든 암호를 깨는 방법을 발견했다. 그 방법은 빈도를 조사하는 것이다. 창영이는 말할 수 없는 방법을 이용해서 현우가 강산이에게 보내는 메시지를 획득했다. 이 �� www.acmicpc.net 문제가 어렵거나, 구현이 어려운 문제는 아니지만. 제출시 오류가 났다... 한참 오류난 포인트를 찾았는데.. 핵심은 수열의 두 수 X와 Y가 있을 때, X가 Y보다 수열에서 많이 등장하는 경우에는 X가 Y보다 앞에 있어야 한다. 만약, 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다. 이렇게 정렬하는 방법을 빈도 정렬이라고 한다. '만약, ~~' 부터가 오류의 원인이다. 수열내 등장한 개수..