www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 한줄 후기 : 골 4 맞어?! 하루에 하나만 강연 할 수 있을 때 pay를 가장 많이 받을 수 있는 방법을 찾으면 된다. 처음에 우선순위 큐인걸 알고 바로 짰다가 예외 케이스를 간과해서 틀렸다. 예외 케이스는 3 10 2 10 2 3 1 이러면 13이 아니라 20이 답이다. 왜냐면 2일안에 할 수 있는 강연은 1일날 해도 되니까 정답은 10+10 = 20 이다. //AC //..

www.acmicpc.net/problem/21318 21318번: 피아노 체조 피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 www.acmicpc.net 한줄 후기: 난 피아노 체르니 40까지 배웠다. x, y 범위 내에서 a[i] > a[i+1] 인 개수를 찾는 문제이다. 다만 완전 탐색처럼 풀면 test case 별로 for 문을 돌아서 시간초과가 난다. 어떻게 알았냐면 나도 알고 싶지 않았다. //AC //BOJ 21318 피아노 체조 #include #include using namespace std; vector piano; int cnt[10101..

www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 한줄 후기 : 덱이 진짜 편한거 같어 신촌 겨울 알고리즘 캠프 초급 모의고사 문제다. 저번에 한번 심심해서 풀어봤다. 문제 이해는 참 쉬웠는데 은근 뭐로 접근해야할 지 고민한 문제. 그러다 덱을 써보자 하고 덱을 써서 풀었다. 길이가 20만이라 당연히 완전탐색은 무리다. //AC //BOJ 20922 겹치는 건 싫어 #include #include using namespace std; deque dq; i..

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개만큼..

이 블로그는 진짜 아무도 안보지만.. 그래서 주저리 할 수 있습니다. 혹시나 검색해서 들어오셨다면 저는 그리 높은 등수를 받은 팀이 아니라 혹시 대회 문제들에 대한 다양한 풀이를 보고 싶으시면 다른 블로거 분 글을 보시는 게 좋을 것 같습니다. 2/28에 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2021 Winter) 에 참가했습니다. SUAPC는 서강대, 숙명여대, 연세대, 이화여대, 홍익대 ICPC 동아리 연합에서 개최하는 대회인데, 제가 속해있었던 알고스가 여기 소속입니다. 사실 그 전에 알고리즘 캠프 중급반을 듣고 캠프 콘테스트에도 참가했지만 여긴.. 부끄럽지만 열심히 하진 않았어요.. 거두절미하고 결론만 말하면 대회에서는 25등/52팀 이란 결과를 얻었습니다. 대회에 ..