2025-03-12 PS

 

스트릭 채우기용 : 26711 

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

그냥 큰 수 덧셈. 파이썬을 이용해서 풀어주었다. 그닥 중요한건 아니라서 코드는 따로 안 올림

타일 교체 (17622, G3)

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

k = 0

이때는 올바른 입구로 들어가는지 확인하고 트랙 따라서 가면서 마지막에 올바른 출구로 나가는지 확인해주면 된다. 저 강조 표시해둔 부분이 굉장히 빼먹기 쉬워서 생각보다 어려웠다. 최대 N^2칸을 지날 수 있으므로 시간복잡도는 O(N^2).

k = 1

N≤50이기 때문에, 모든 칸을 다 한번씩 바꿀 수 있는 형태로 바꿔주면서 되는지 일일이 확인하고 최단 경로를 구하는 방법이 통한다. 이 방법은 모든 칸(N^2)을 한번씩 바꿀 수 있는 형태(5가지)로 바꿔주면 5*N^2, 확인할 때 k=0일때와 동일하게 N^2칸을 지나므로 시간복잡도는 O(5*N^4). 구현할 때 주의해야 할 점은 k=1이면 반드시 하나를 다른 타일로 바꿔줘야한다는 점이다. 나 같은 경우에는 그 조건을 신경을 안쓰고 같은 타일로 바꿀 수 있는 코드를 짰다가 한 번 틀렸다.

 

Code : https://github.com/djayy035/dj035_PS/blob/main/Baekjoon/17622.cpp

 

피하자 (25379, S4)

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

그냥 홀수 / 짝수 의 경우와 짝수 / 홀수의 경우로 나누어서 잘 세어주면 된다.

어차피 짝수 홀수 두 종류라서 한 숫자당 이동 횟수는 앞에 있는 다른 숫자의 갯수이기에 누적합을 이용해서 세주면 된다.

 

앞으로 골드 미만의 문제는 풀이를 매우 짧고 간결하게 할듯

Code : https://github.com/djayy035/dj035_PS/blob/main/Baekjoon/25379.cpp

 

제자리 (25400, B1)

그냥 값이 1인 변수를 잡고 배열 순서대로 보면서 변수와 같으면 증가시키는 식으로 남길 수 있는 최대 카드 갯수를 구하면 답을 식을 세워 계산할 수 있다.

 

Code : https://github.com/djayy035/dj035_PS/blob/main/Baekjoon/25400.cpp

 

 XOR 최대 (32073, P4)

일단 문제를 보고 관찰한 점은 다음과 같다

- s1, s2중에서 하나는 무조건 S여야 한다.

- S를 이진수로 나타냈을 때 왼쪽에 있는 0을 채울수록 더 이득이다.

-최대한 왼쪽에 있는 자리를 1번이라고 할때, 최대한 왼쪽에 있는 0의 위치를 n번이라고 하면 최적이 될 수 있는 답의 후보는 n-1개이다.

 

이때 최대한 왼쪽에 있는 0의 왼쪽에 있는건 다 1이므로 왼쪽에 있는 1을 얼마나 사용할지가 관건인데 그리디하게 생각하면 최대한 왼쪽에 있는 0에서 0이 연결된 만큼 1을 이용해주어서 XOR을 했을 때 그 연속된 0들이 다 1로 되게 하는게 최적이다.

 

대충 증명을 하면,

더 적게 이용하면 당연히 연속된 0들 중에서 아직 0인게 있으므로 연결된만큼 1을 이용하는 것보다 더 작은 값이 된다.

더 많이 이용하면 연속된 0들 이후에는 당연히 1이 있을건데 연속된 0들보다 1을 더 많이 사용하게 되므로 당연히 그 이후에 있는 1에 XOR을 하면 그 자리는 0이 될수밖에 없다. 반면에 0이 연결된만큼만 1을 사용해주면 그 다음 자리끼리 XOR을 하면 당연히 그 자리는 1이므로 연속된 0들만큼 채우는 게 best이다.

 

Code :  https://github.com/djayy035/dj035_PS/blob/main/Baekjoon/32037.cpp

 

CF Round #1004 (Virtual Contest)

 

3솔

오랜만에 해서 제대로 힘을 발휘하지는 못했지만 그래도 블루퍼포임에 기쁘다. 

C 뇌절만 안했더라도 D를 풀었을텐데 아쉽다.

 

A -

자릿수의 합이 어떻게 변하는지를 관찰하면, 

S(n)<S(n+1) : 그냥 S(n+1) - S(n) = 1이다.

S(n)>S(n+1) : 이때 n은 ...99의 형태일텐데 9의 갯수만큼 0으로 변하고 그 다음 자릿수가 1만큼 증가하므로 연속된 9의 갯수를 m이라고 하면 S(n) - S(n+1) = 9*m-1이다. 즉, 차이를 9로 나눈 나머지가 8이라는 것.

 

Code : https://github.com/djayy035/dj035_PS/blob/main/Codeforces/Codeforces%20Round%201004%20(Div.%202)/A.cpp

 

B -

바구니끼리 서로 같은 수들로 이루어지려면 존재하는 숫자 종류들이 다 짝수개여야한다.

큰 수를 뺄 수는 없지만 작은 수를 더할 수 있고, 같은 수가 최소 2개 이상이여야 하므로, 최대한 작은 수들을 더해서 큰 수들 쪽에 같은 숫자들을 최대한 많이 추가해주어서 가장 큰 숫자가 짝수개, 나머지는 2개로 맞춰준다. 이유는 2개만 있을때에는 하나를 더하면 다른 하나는 홀수개로 그대로 있어야하기 때문이다. 

 

Code : https://github.com/djayy035/dj035_PS/blob/main/Codeforces/Codeforces%20Round%201004%20(Div.%202)/B.cpp

 

C -

9로만 이루어진 숫자들은 결국 10^n-1꼴이고, 결국엔 9로 이루어진 엄청 큰 숫자를 10 이상의 숫자에 7번 더하면 무조건 앞자리수가 7이기에 무조건 7이므로, n-k (0<=k<7)의 자릿수에서 k번 이하로 7을 만들 수 있는 자릿수가 존재하면서 최소인 k를 구하면 된다.

 

Code : https://github.com/djayy035/dj035_PS/blob/main/Codeforces/Codeforces%20Round%201004%20(Div.%202)/C.cpp

 

Upsolving

 

D - 

배열에서의 최댓값을 mx, 최솟값을 mn이라고 하면,

i) mx-mn = n-1

이때 맨헤튼 거리면 대답은 무조건 n-1 이상이고, 그래프이면 n-1 이하이다.

대답이 n-1일때는 그래프가 단방향 그래프이므로 물어본 순서를 반대로 하면 간선이 n개이기 때문에 무조건 n-1이 나올 수 없다. 맨헤튼 거리는 순서는 바꾸든 말든 똑같으므로 이를 이용해주면 된다.

 

ii) 나머지 경우

이때는 중복된 값이 x에 존재한다는 건데, 생각해보면 중복된 값이 나온다는 건 최소 하나의 숫자가 안나온다는 것이며, 그 숫자의 경우 다른 노드로 갈 수 있는 단방향 간선이 없으므로 그 숫자를 시작점으로 해서 물어봐서 답이 0이면 그래프임이 명확해진다.

 

Code : https://github.com/djayy035/dj035_PS/blob/main/Codeforces/Codeforces%20Round%201004%20(Div.%202)/D.cpp

 

E는 내일 업솔빙 해서 올릴 예정이다.