Doby's Lab

https://www.acmicpc.net/problem/1004 1004번: 어린 왕자 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주 www.acmicpc.net Level: Silver III Solved By: Geometry $$ (x-a)^2 + (y-b)^2 = r^2 \; (a, b = Center\;points)$$ 원의 방정식을 이용해 풀었습니다. x와 y에 값을 대입했을 때 r^2보다 작으면 내부, 크면 외부인 점을 활용합니다. (겹치는 점은 안 주어진다 함) 시작점과 도착점 둘 다 내부에 있는 경우와 외부에 있는 경우는 안 ..

https://www.acmicpc.net/problem/1769 1769번: 3의 배수 문제가 잘 풀리지 않을 때, 문제를 바라보는 시각을 조금만 다르게 가지면 문제가 쉽게 풀리는 경험을 종종 해 보았을 것이다. 여러 가지 방법이 있지만 그 중 하나로 우리가 풀고 싶은 문제를 www.acmicpc.net Level: Silver V Solved By: String 자릿수가 엄청 크기 때문에 문자열로 변수를 받아서 각 자리를 더할 때, 정수형으로 변환시켜서 계산해주면 됩니다. cal 함수에서 sum 변수에 대해 overflow가 나지 않는 이유는 최대 자릿수가 1,000,000이고, 자릿수마다 최대로 가질 수 있는 수는 9인데 이를 다 더하면 9,000,000이기에 overflow는 나지 않습니다. #i..

https://www.acmicpc.net/problem/1448 1448번: 삼각형 만들기 첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 www.acmicpc.net Level: Silver III Solved By: Geometry 삼각형이 되는 조건을 이용합니다. 세 변이 주어졌을 때, a, b, c가 오름차순으로 커진다고 합시다. 그럼 a + b > c가 되어야 하는 조건을 이용하여 문제를 풀 수 있습니다. 변이 주어지면 내림차순으로 정렬하여 순서대로 3개의 원소를 골라서 삼각형의 조건을 만족하면 break를 걸어 세 변의 합을 출..

https://www.acmicpc.net/problem/1331 1331번: 나이트 투어 나이트 투어는 체스판에서 나이트가 모든 칸을 정확히 한 번씩 방문하며, 마지막으로 방문하는 칸에서 시작점으로 돌아올 수 있는 경로이다. 다음 그림은 나이트 투어의 한 예이다. 영식이는 6× www.acmicpc.net Level: Silver V Solved By: Implementation 3가지 조건을 따져주어야 합니다. 나이트로 이동 가능한가? 방문했던 곳을 다시 방문하지 않는가? 마지막 나이트가 처음 나이트로 갈 수 있는가? 섣불리 코드를 썼다가 틀릴 수도 있는 문제입니다. #include #include #define pii pair using namespace std; vector chess; struc..

https://www.acmicpc.net/problem/10266 10266번: 시계 사진들 상근이는 보통의 시계와는 다른 독특한 시계 사진 두장이 있습니다. 시계는 n개의 동일한 길이와 목적을 가진 시계 바늘들을 가지고 있습니다. 애석하게도 시계의 숫자들은 희미해져 각 시계 바 www.acmicpc.net Level: Platinum IV Solved By: KMP 우선 각도들이 크기에 상관없이 랜덤 하게 주어지기 때문에 정렬을 해줄 필요가 있습니다. 시계 모양이 같다는 건 시침을 모두 두었을 때 인접한 시침마다의 각이 같다는 것을 뜻합니다. 즉, 정렬한 배열의 인접한 수들의 차를 구하여 새로운 배열을 만들면 됩니다. vector process(vector& v){ vector ret; for(int..

https://www.acmicpc.net/problem/3295 3295번: 단방향 링크 네트워크 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 상호 네트워크를 이루는 노드의 수 n과 단방향 링크의 수 m이 주어진다. (n ≤ 1,000, m ≤ 50,000) 노드는 0번부터 n-1 www.acmicpc.net Level: Platinum II Solved By: Bipartite Matching, Hopcroft Karp 문제의 내용을 요약하면 링을 구성하는 노드의 개수와 선형 배열의 노드의 개수 - 1을 구하라는 뜻입니다. 여기서 파악해야 할 것은 링의 구성 노드가 N 개라면 간선도 N 개라는 것, 그리고 선형 배열의 노드 개수가 N 개라면 간선은 N - 1개라는 ..

https://www.acmicpc.net/problem/1671 1671번: 상어의 저녁식사 어떤 상어는 저녁식사로 서로를 먹는다. 모든 상어는 자신과 다른 상어의 크기, 속도, 지능을 수치로 나타낸 것을 알고 있다. 만약, 상어 A의 크기, 속도, 지능이 상어 B의 크기, 속도, 지능보다 크 www.acmicpc.net Level: Platinum III Solved By: Bipartite Matching, Edmonds Karp 잡아먹는 상어와 잡아먹히는 상어들을 이분 그래프로 나누어줍니다. 여기서 제가 원하는 네트워크는 소스로부터 잡아먹는 상어들에게 capacity 2를 주며 연결하고(한 상어당 2개까지 먹을 수 있기 때문), 잡아먹는 상어들이 잡아먹히는 상어들을 잡아먹을 수 있다면 capcit..

이번 대회는 2 솔브로 마무리하고, 풀 수 있을 거 같던 애매했던 두 문제(C, D)까지 풀고 난 후, 4가지 문제까지만 솔루션을 작성해보려 합니다. 대회가 끝난 직후의 포스팅에서도 말했지만 대회는 자신의 약점을 객관적으로 볼 수 있게 하고, 이를 보완할 수 있는 좋은 기회가 되는 거 같습니다. 나머지 E, F, G, H는 쓰여졌던 알고리즘들을 더 공부하여 보완해보려 합니다. 정확히는 쓰인 알고리즘들이 어떻게 응용되는가가 주목할 점이라 생각합니다. 대회 문제 링크: https://www.acmicpc.net/category/detail/3231 4th UNIST Algorithm Programming Contest Uni-CODE 2022 www.acmicpc.net A. 가장 긴 막대 자석 🤔 문제의 ..