복귀

https://www.acmicpc.net/problem/20649 한 소가 다른 소에 의해 풀을 먹지 못하는 관계를 트리로 생각한다면, 답은 각 노드에서 그 노드를 루트로 하는 트리의 노드 갯수에 1을 뺀 값이라는 걸 알 수 있다.x, y좌표가 서로 다 다르므로 같은 방향이면서 같은 x, y 좌표인 경우를 배제할 수 있다.그렇다면 같은 방향으로 가는 소들은 서로 영향을 미치지 않는다. 그럼 서로 다른 방향으로 가는 소들을 생각해보면,동쪽 방향으로 가는 소의 시작 좌표를 (x1, y1)이라고 하고, 북쪽 방향으로 가는 소의 시작 좌표를 (x2, y2)라고 하자.그렇다면 x1y2일때 서로 만나서 한 마리가 정지하거나 서로 갈 길 간다는 걸 알 수 있다.그러나 소들의 위치에 따라 소들의 충돌 관계가 달라지므..

수 고르기 (S4)어차피 K개의 수를 어떻게 고르든 빼는 값은 변하지 않으므로 배열에서 가장 큰 원소 K개를 골라주면 된다. Code : https://github.com/djayy035/dj035_PS/blob/main/Baekjoon/20186.cpp꿀 따기 (G5)벌집이 맨 왼쪽, 맨 오른쪽, 가운데인 경우를 나누어서 풀어주면 된다.가운데인 경우 벌집은 맨 왼쪽과 오른쪽을 제외한 최댓값이 있는 곳에 배치한다. Code : https://github.com/djayy035/dj035_PS/blob/main/Baekjoon/21758.cpp달려달려 (G4)dp(i, j) = i분에 피로도 j일때 최대로 멀리 갈 수 있는 거리쉬는 경우와 뛰는 경우를 나누어서 식을 세우면 된다. 쉴 때 피로도가 무조건 0..

매직스퀘어 (S5, K512)그냥 조건에 맞는대로 짜면 된다. 주의해야 할 점은 구현할 때 숫자가 겹치는지 확인 할 때 배열 크기가 충분한지를 잘 확인해야한다. Code : https://github.com/djayy035/dj035_PS/blob/main/Baekjoon/15739.cpp스케이트 연습 (S4)속도는 마음대로 올릴 수 있으나 마음대로 내릴수는 없고 처음과 끝 모두 속도가 0이어야 하므로 끝점서부터 시작하여 각 지점에서 낼 수 있는 최대 속도를 구해준다.  Code : https://github.com/djayy035/dj035_PS/blob/main/Baekjoon/28324.cpp 대피소 (S4)N이 매우 적으므로  K=1, 2, 3에 따라 그냥 모든 경우의 수를 다 돌아보면 된다. C..

스트릭 채우기용 : 26711 https://www.acmicpc.net/problem/26711그냥 큰 수 덧셈. 파이썬을 이용해서 풀어주었다. 그닥 중요한건 아니라서 코드는 따로 안 올림타일 교체 (17622, G3)https://www.acmicpc.net/problem/17622k = 0이때는 올바른 입구로 들어가는지 확인하고 트랙 따라서 가면서 마지막에 올바른 출구로 나가는지 확인해주면 된다. 저 강조 표시해둔 부분이 굉장히 빼먹기 쉬워서 생각보다 어려웠다. 최대 N^2칸을 지날 수 있으므로 시간복잡도는 O(N^2).k = 1N≤50이기 때문에, 모든 칸을 다 한번씩 바꿀 수 있는 형태로 바꿔주면서 되는지 일일이 확인하고 최단 경로를 구하는 방법이 통한다. 이 방법은 모든 칸(N^2)을 한번씩 ..

https://www.acmicpc.net/problem/18785 18785번: Clock Tree In this example, Bessie can set all the clocks to point to 12 if and only if she starts in room 2 (for example, by moving to room 1, 2, 3, 2, and finally 4). www.acmicpc.net 상당히 어려운 문제였다.. 먼저 우리는 이러한 통로를 가면서 맞춰놓을 때, 처음 노드에서 출발해서 다시 돌아오는 방식임을 알 수 있다. 이때 왔다갔다 하면서 관찰할 수 있는 건 어떤 노드와 그 주변 노드가 하나 있을 때 둘 다 자신을 다 12시로 맞추기 위해서는 자신과 1차이나는 노드가 항상 있어야..