onaeonae1

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 문제 설명 두 사람의 키를 비교한 관계들이 쭉 주어질 때 (가능한) 키 순서를 출력하면 되는 문제 문제 풀이 -그래프에서 정해진 노드끼리의 간선등 정해진 순서가 있을 때, 이를 위반하지 않으면서 그래프 전체의 노드를 방문하는 경우를 가져오는게 위상정렬 문제의 특징이다. -위의 문제는 기본적인 위상정렬 문제라서 크게 변형할 것이 없었다. 바로 연결 관계 받고, 위상 정렬 구현해..

www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 설명 물건 갯수 n 과 가방에 담을 수 있는 무게 제한 k가 주어질 때, 주어지는 물건들에 대해 가능한 최대 가치를 찾으면 되는 냅색 문제이다. 즉, DP로 슥 돌리면 해결할 수 있다. 문제 접근 작년 이맘때 쯤 열심히 들었던 알고리즘이 생각나는 문제였다. 그때 이거랑 정확히 같은 문제를 이론적으로 봤었다. DP[k] : 무게 k일때의 최대..

https://www.acmicpc.net/problem/17827 17827번: 달팽이 리스트 첫째 줄에 노드의 개수 N(2 ≤ N ≤ 200,000), 질문의 횟수 M(1 ≤ M ≤ 200,000), N번 노드가 가리키는 노드의 번호 V(2 ≤ V ≤ N)가 공백으로 구분되어 주어진다. 둘째 줄에 N개의 정수 C1, C2, …, CN이 공백 www.acmicpc.net 굉장히 쉽고 힌트에 나와있는 부분에 대한 예외처리(민달팽이)를 해줄 필요 없이 바로 일반항을 구해줄 수 있다. N M V가 주어지고, num번째 수가 궁금할때, num=N인 경우의 정답을 target이라고 했을 때, target = (num-N) % gap + V 이다. 이때 gap은 (N-V+1) 이다. 말로 이렇게 쓰니까 상당히 직..

www.acmicpc.net/problem/3665 3665번: 최종 순위 문제 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 �� www.acmicpc.net 문제를 제대로 해석하지 못해서 좀 고생했다. 문제의 조건을 풀어서 설명하면 다음과 같다. 기존의 순서가 주어지고, 이후 상대적인 순서의 변경이 주어질 때, 변경된 순서대로 출력 만약 불가능하다면, IMPOSSIBLE 출력 처음에 주어진 순서대로 연결해주고, 이후 변경된 순서를 적용시켜서 연결, 진입차수를 수정해주면 된다. 처음 연결에서 인접행렬을 짜듯이 하나하나 연결을 해줘야 하는게 중요하다. 예를 ..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 이번에도 위상정렬을 쓰는 문제다. 위상정렬을 쓰는 문제들은 그래프에서 순서가 주어지는데, 이 문제에서는 하나의 조건이 더 추가된다. 일단 문제를 풀어 써보자. 1~N까지 총 N개의 문제들로 구성된 문제집이 있다. 1이 가장 쉽고, N이 가장 어렵다.(=번호가 낮을 수록 쉬운 문제이다.) 그리고 주어지는 조건은 다음과 같다. N개의 문제를 모두 풀어야 한다. 주어진 순..

https://www.acmicpc.net/problem/17828 17828번: 문자열 화폐 첫 번째 줄에 문자열의 길이 N(1 ≤ N ≤ 5,000,000)과, 문자열의 가치를 나타내는 정수 X(1 ≤ X ≤ 500,000,000)가 공백으로 구분되어 주어진다. www.acmicpc.net 그리디로 쉽게 풀어줄 수 있다. 문제를 풀어 설명하자면 다음과 같다. 문자열 A~Z를 1~26이라고 했을 때, 이들을 모두 더한 것을 문자열 화폐라고 한다. 즉 AAABB 같은 경우 1+1+1+2+2 = 7 이때 길이 N이면서 가치는 M을 갖는 문자열을 구성하라는 것이다. 그러니까 위의 문자열은 N=5 M=7 일때의 정답이다. 이를 풀어주는 방법은 위에서 말한대로 그리디를 쓰면 된다. 길이 N만큼을 전부 A로 채우..