Doby's Lab

https://www.acmicpc.net/problem/1094 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대 www.acmicpc.net Solved By: Math 문제를 해석하면 주어진 수가 몇 개의 2의 제곱수로 이루어져 있는지 묻는 문제였습니다. 이진수에 의하면 모든 수는 이진수로 표현 가능하기 때문에 이런 특성을 활용하여 아이디어를 떠올릴 수 있었습니다. #include using namespace std; int main(){ int n; cin >> n; int two = 64; int ans = 0; while(t..

https://www.acmicpc.net/problem/1213

https://www.acmicpc.net/problem/14401 14401번: 악덕 나라 남규 나라의 왕 zych는 도로 정비 계획을 만들고 있다. 남규나라의 도시는 2차원 평면에 존재하며, 각 도시는 (xi,yi)에 위치한다. 새롭게 고속도로를 만들어 모든 도시를 고속도로를 통하여 다른 www.acmicpc.net Solved By: Kruskal, CCW 좌표값이 존재하여 좌표 간의 거리를 구한 후, 최댓값을 구하기 때문에 Edge의 비용을 음수 값으로 바꾸어주고, 이미 있는 고속도로라면 두 노드를 union 하여 거리를 구한 Edge들을 Kruskal 돌리면 되는 간단한 문제일 줄 알았습니다. 하지만, 문제에서 "고속도로 하나하나는 다른 도시들을 거치지 않아야 하며"라는 조건이 있기 때문에 이를..

https://www.acmicpc.net/problem/1143 1143번: 경찰 첫째 줄에 마을의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 마을부터 경찰서를 설치하는데 드는 비용이 주어진다. 이 값은 1000보다 작거나 같은 자연수이다. 셋째 www.acmicpc.net Solved By: SCC 몇 달 전 이 문제를 시도했을 때와 이번에 시도했을 때 막혔던 부분의 코드를 비교해보니 똑같더군요. 하지만, 이번엔 관점을 좀 다르게 잡았습니다. SCC 코드에 문제가 있는 게 아닐까 싶어 코드를 뜯어보던 반면 이번엔 이전부터 같은 SCC 코드를 사용하는데 뭐가 문제겠냐 싶어서 평균값에 초점을 두었습니다. 이 문제를 푸는 방법은 SCC를 통해 어느 한 SCC의 indeg..

https://www.acmicpc.net/problem/1064 1064번: 평행사변형 평행사변형은 평행한 두 변을 가진 사각형이다. 세 개의 서로 다른 점이 주어진다. A(xA,yA), B(xB,yB), C(xC,yC) 이때, 적절히 점 D를 찾아서 네 점으로 평행사변형을 만들면 된다. 이때, D가 여러 개 나 www.acmicpc.net Solved By: Geometry, CCW CCW를 통해 세 점들이 한 직선 위에 있는지 판별하여 평행사변형을 만들 수 있는지 없는지에 대해 1차적으로 구분합니다. 나머지는 세 점들로부터 두 점씩 짝지어 거리를 구하여 구할 수 있는 모든 평행사변형의 둘레를 구한 다음 최댓값과 최솟값의 차이를 구해줍니다. #include #include #include #defin..

군생활 도중에 이런 목표를 이뤄낼 수 있을 거라 생각하지 못했습니다. 목표 중 꽤나 큰 목표였던 백준 다이아몬드를 달성했습니다. 이때까지의 PS에 관해서 생각이 많았던 만큼 할 말도 많아서 두 파트로 나누어 첫 번째 파트는 어떻게 달성했는지에 대한 표면적인 이야기를 다루고, 두 번째 파트에서는 어떤 생각들을 가지고 있었는지에 대해 이야기해보려 합니다. Part 1: Outside 이론을 넘은 응용 누군가 어떻게 풀었든 간에 겸손할 것 이론을 넘은 응용 티어를 달성할 때마다 깨닫는 것들이 있습니다. 이번에 깨달은 것은 이때까지 모호하던 말이 명확해졌기 때문에 적어봅니다. 한 알고리즘의 이론에 대해 공부를 하고, 구현을 하는 데까지 성공하면 바로 알고리즘을 적용해서 문제를 풀고 싶어 집니다. 하지만, 1~2..

https://www.acmicpc.net/problem/10531 10531번: Golf Bot Do you like golf? I hate it. I hate golf so much that I decided to build the ultimate golf robot, a robot that will never miss a shot. I simply place it over the ball, choose the right direction and distance and, flawlessly, it will strike the ball across www.acmicpc.net Solved By: FFT 문제가 영어로 되어있어서 간단히 요약하자면 N개의 정수가 주어지는데 뒤이어 주어지는 M개의 정수를 N..

https://www.acmicpc.net/problem/18134 18134번: 치삼이의 대모험 첫 번째 줄에 골목길의 교차점 개수 N(3 ≤ N ≤ 1,000)과 골목길의 개수 M(3 ≤ M ≤ 10,000)이 주어진다. 두 번째 줄부터 M개의 줄에 골목길의 정보가 주어진다. 각 줄에는 3개의 정수로 골목길의 www.acmicpc.net Solved By: Network Flow, MCMF 이 문제는 2311번(https://www.acmicpc.net/problem/2311)과 29900번(https://www.acmicpc.net/problem/22990)에서 유사한 테크닉으로 풀 수 있었습니다. 왕복을 해야 한다는 점에서 SOURCE로부터 시작 노드로 Capacity가 2가 되도록 Edge를 잡..