www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 한줄 후기 : 앞으로 모든 문제가 n 제한 100이면 좋겠다. 문제를 짧게 설명하자면 1~n 노드까지 중에 수색범위 m 이내로 다른 노드에 가서 아이템을 주워올 수 있는데 어떤 노드에 내려서 얻을 수 있는 아이템 합 중 최대를 찾으면 되는 문제입니다. //AC //BOJ 14938 서강그라운드 #include #define INF 987654321 using namespace std; int item[101]; in..
www.acmicpc.net/problem/20924 20924번: 트리의 기둥과 가지 첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다. 이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번 www.acmicpc.net 한줄 후기: 코드가 너무 더러운 것 같다.. //AC //BOJ 20924 트리의 기둥과 가지 #include #include using namespace std; vector v[200001]; int visit[200001]; int gi = 0, gidoong, ans = 0; void dfs..
www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 한줄 후기 : 전에 못 풀던 문제를 다시 풀었는데 맞으면 진짜 기쁘다 문제를 잘 읽어보면 결국 한 팀이 된다는건 4->7->6->4 이렇게 한팀 즉, 그래프로 생각했을 때 사이클이 만들어지면 한 팀이 되는 것이다. 그럼 팀에 속하지 못한 학생의 수이니 사이클 탐지를 하며 개수를 세어 전체 수에서 빼주면 답이 된다. //AC //BOJ 9466 텀 프로젝트 #include #include #include using n..
www.acmicpc.net/problem/20955 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net 한줄 후기: 수술은 의사에게.. 그래프 문제처럼 보인다. 처음의 mst 관련인가 하고 생각했는데 문제를 읽어보니 대충 연결 요소의 개수를 구해주면되는 거 아닌가? 하고 바로 코드를 작성했다. 틀렸다! 다시 문제를 읽어보니 민서가 할 수 있는 연산이 2개이다. 난 이중 뉴런끼리 연결을 끊는 연산을 간과했다. 뉴런끼리 연결을 끊어야만 하는 경우가 언제일까? 사이클이다! 민서는 트리를 만들고 싶어하는 것이니 사이클..
www.acmicpc.net/problem/20956 20956번: 아이스크림 도둑 지호 지호는 매일 아이스크림 가게에 방문한다. 아이스크림을 먹던 지호는 놀라 자빠질 수밖에 없었다. 실수로 민트초코 맛을 먹었기 때문이다. 대다수의 사람은 치약 맛이 난다는 이유로 민트초코 www.acmicpc.net 한줄 후기 : 백준에도 드디어 오마이걸이.. 기뻐하는 미라클 요새 졸업작품 때문에 백준은 거의 안들어가는데 한번 들어갔다가 '지호'를 보고 멈칫.. 집에서 한번 풀어보았다. 문제는 처음에 살짝 복잡했는데 요약하자면 지호가 아이스크림을 먹을 때 가장 양이 많은 것을 왼쪽에서 부터 먹는다. 이때 양이 7의 배수인 아이스크림은 민트 초코로 이를 먹으면 지호가 화가나서 아이스크림을 좌 우로 뒤집는다. 이제 M개만큼..
www.acmicpc.net/problem/2912 2912번: 백설공주와 난쟁이 첫째 줄에 난쟁이의 수 N과 모자 색상의 수 C가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ C ≤ 10,000) 둘째 줄에는 각 난쟁이가 쓰고 있는 모자의 색상이 줄을 서 있는 순서대로 주어진다. 셋째 줄에는 사진 www.acmicpc.net 한줄 후기 : 세그 트리라도 푼게 어디야.. 원래 확률적 알고리즘 파트라서 Mo's Algorithm 을 이용해 풀어봐야 하는 것 같다. 하지만.. 도저히 못풀겠음 구글링 좀 해서 봤는데 계속 시간 초과 나서 못 풀었다. 그래서 이 문제를 또 풀 수 있는 방법인 세그먼트 트리를 이용해 풀었다. 세그먼트 트리로 푸는 법은 간단하다. 그냥 처음 트리를 생성할 때, 트리에는 해당 ..
www.acmicpc.net/problem/11004 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 한줄 후기 : ㅂㅇㅎ 교수님 수업 같다 신촌 알고리즙 중급 연습 문제 였는데 확률적 알고리즘 파트에서 Quick Select를 알려주셔서 그거로 풀었다. 사실 풀고 찾아보니 대부분은 그냥 c++ sort 라이브러리로도 잘 풀린다고 한다. 아 그리고 c++에 아예 Quick Select를 구현해 놓은 라이브러리도 있다는데 그걸 쓰지는 않았다. Quick Select는 Quick Sort를 구현하면서 빠르게 n번째 원소를 찾는 기법이라고 한다. 실제 Sort는 대부분..
www.acmicpc.net/problem/8201 8201번: Pilots In the first line of the standard input two integers are given, t and n (0 ≤ t ≤ 2,000,000,000, 1 ≤ n ≤ 3,000,000), separated by a single space, denoting the tolerance level and the number of yoke's position measurements taken. The second line give www.acmicpc.net 한줄 후기 : 영어 해석은 papago.. 신촌 알고리즘 중급 캠프 덱 DP 강좌 필수 문제였다. 사실 필수 문제를 다 읽어봤는데 (다이아는 보지도 않음) 내가 ..
www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 한줄 후기 : solved ac class 5를 따기 위한 눈물 겨운 여정.. 문제를 읽으면서 건물 짓는 순서가 주어지길래 위상정렬인 것 같다고 생각하고 풀었다. //AC //BOJ 1516 게임 개발 #include #include #include using namespace std; int ind[501]; int ans[501]; int c[501]; vector v[501]; void topo..
