PS(68)
-
[USACO] Stuck in a Rut (Silver)
https://www.acmicpc.net/problem/20649 한 소가 다른 소에 의해 풀을 먹지 못하는 관계를 트리로 생각한다면, 답은 각 노드에서 그 노드를 루트로 하는 트리의 노드 갯수에 1을 뺀 값이라는 걸 알 수 있다.x, y좌표가 서로 다 다르므로 같은 방향이면서 같은 x, y 좌표인 경우를 배제할 수 있다.그렇다면 같은 방향으로 가는 소들은 서로 영향을 미치지 않는다. 그럼 서로 다른 방향으로 가는 소들을 생각해보면,동쪽 방향으로 가는 소의 시작 좌표를 (x1, y1)이라고 하고, 북쪽 방향으로 가는 소의 시작 좌표를 (x2, y2)라고 하자.그렇다면 x1y2일때 서로 만나서 한 마리가 정지하거나 서로 갈 길 간다는 걸 알 수 있다.그러나 소들의 위치에 따라 소들의 충돌 관계가 달라지므..
2025.09.12 -
2025-03-14 PS
수 고르기 (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..
2025.03.14 -
2025-03-13 PS
매직스퀘어 (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..
2025.03.14 -
2025-03-12 PS
스트릭 채우기용 : 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)을 한번씩 ..
2025.03.13 -
BOJ 18785 : Clock Tree
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차이나는 노드가 항상 있어야..
2022.09.03 -
2022.07.31 PS
jjang36524가 만든 셋을 4시간으로 잡고 풀었다. 점수는 138점으로 처참하였다. 결과는 0 100 0 38 이었다. A번 같은 경우는 솔직히 좀 더 집중했더라면 0점 초과의 점수를 받지 않았을까 싶다. 그렇게 위로함을 뒤로하고 A 업솔빙, D는 이미 풀었던 문제를 복습하고 나서 풀이만 떠올렸다. B(12763). 지각하면 안돼 처음엔 그냥 쉬운 다익스트라 문제인 줄 알았는데 크게 데였고, dp로 접근하여 다시 맞았다. dp(i,j) = 지금 i호관에 있고 남은 돈이 j일때 답 이걸 가지고 식을 잘 세우면 된다 코드를 너무 더럽게 짠 것 같다... 코드 A(11941). 핀볼 문제에서 각 끝에서 온 공은 모두 특정 한 곳으로 떨어진다는 중요한 관찰 하나를 해야 한다. 그렇다면 여기서 우리는 비용이..
2022.08.01