[코드포스] Codeforces Round #640 (Div. 4)
대회 링크: https://codeforces.com/contest/1352
A번 문제: https://codeforces.com/contest/1352/problem/A
[ 문제 해설 ]
이 문제는 먼저 각 자릿수를 확인하면 된다. 이 때, 0이 아닌 자릿수에 대하여 그 값들을 출력해주면 된다. 예를 들어 입력이 6009이라면, 6000과 9를 출력하면 된다. 소스코드는 다음과 같다.
[ 정답 코드 ]
for _ in range(int(input())):
n = int(input())
result = []
power = 1
# 각 자릿수를 확인하며
while n > 0:
# 0이 아닌 자릿수에 대하여
if n % 10 != 0:
# 그 값들을 각각 출력
result.append((n % 10) * power)
n //= 10
power *= 10
print(len(result))
for i in result:
print(i, end=' ')
print()
B번 문제: https://codeforces.com/contest/1352/problem/B
이 문제는 k개의 수를 더해서 n을 만들 수 있는지 물어보는 문제이다. 단, k개의 수는 모두 홀수이거나 모두 짝수여야 한다.
[ 문제 해설 ]
문제에서 요구하는 대로 모든 수가 홀수이거나, 모든 수가 짝수인 경우 두 가지만 고려하면 된다.
먼저 모든 수가 홀수인 경우, (k - 1)개의 수를 모두 1로 설정(가능한 작은 수)한 뒤에 '나머지 1개의 수'가 홀수이면서 조건을 만족시킬 수 시 있는지 확인하면 된다. 예를 들어 n = 7, k = 5인 경우에는 (k - 1) + 3 = 7로 n을 만족시킬 수 있다. 즉, 나머지 1개의 수를 3으로 설정하면 된다.
그리고 모든 수가 짝수인 경우, (k - 1)개의 수를 모두 2로 설정(가능한 작은 수)한 뒤에 '나머지 1개의 수'가 짝수이면서 조건을 만족시킬 수 있는지 확인하면 된다. 예를 들어 n = 8, k = 3인 경우에는 (k - 1) * 2 + 4 = 8로 n을 만족시킬 수 있다. 즉, 나머지 1개의 수를 4로 설정하면 된다.
따라서 두 가지 경우만 잘 고려해주는 코드를 작성하면 된다.
[ 정답 코드 ]
for _ in range(int(input())):
n, k = map(int, input().split())
# 모든 수가 홀수인 경우
odd = n - (k - 1)
if odd > 0 and odd % 2 == 1:
print("YES")
for i in range(k - 1):
print(1, end=' ')
print(odd)
continue
# 모든 수가 짝수인 경우
even = n - (k - 1) * 2
if even > 0 and even % 2 == 0:
print("YES")
for i in range(k - 1):
print(2, end=' ')
print(even)
continue
# 두 가지 케이스 모두 만족시킬 수 없을 때
print("NO")
C번 문제: https://codeforces.com/contest/1352/problem/C
n과 k가 주어졌을 때, n으로 나누어 떨어지지 않는 k번째 자연수를 찾으면 되는 문제다.
예를 들어 n = 3, k = 7이라고 하면
1, 2, 4, 5, 7, 8, 10, 11, 13, ...
위와 같이 이어지므로, 7번째 수는 바로 10이 된다.
[ 문제 해설 ]
답을 구하는 방법은 생각보다 쉽다. 구하고자 하는 k번째 자연수는 항상 k 이상이고, 그리고 2k 미만이 된다.
생각해 보면, n = 2일 때는 1, 3, 5, 7, ... 이렇게 갈 텐데, 이 때에도 k번째 수는 2k보다 작은 2k - 1이 된다. 다시 말해 출력해야 되는 정답은 항상 k 이상 2k 미만의 수가 될 것이다. 그렇다면 k보다 얼마나 큰 수가 출력되어야 하는가?
그것은 바로 k보다 (k - 1) // (n - 1)만큼만 커지면 된다. 즉, k + (k - 1) // (n - 1)이 정답이다. 답을 계산하는 방법은 굉장히 다양하지만, 이것보다 간단히 수식으로 표현할 수 있는 답은 없다.
[ 정답 코드 ]
for _ in range(int(input())):
n, k = map(int, input().split())
print(k + (k - 1) // (n - 1))
D번 문제: https://codeforces.com/contest/1352/problem/D
왼쪽에서부터 오른쪽으로 과자를 먹는 사람과 오른쪽에서부터 왼쪽으로 과자를 먹는 사람이 있다.
이 때 한 차례씩 반복하면서 먹어나가는데, 이전 차례에서 상대방이 먹었던 양보다 더 많이 먹어야 하는 방식이다. 그래서 전체 몇 차례나 반복되었는지, 두 사람이 각각 얼마나 먹었는지를 출력하면 된다.
[ 문제 해설 ]
이 문제는 문제에서 요구하는 대로 구현만 잘 해주면 된다. 최대한 깔끔하게 실수 없이 구현해서 정답 처리를 받으면 된다.
[ 정답 코드 ]
for _ in range(int(input())):
n = int(input())
data = list(map(int, input().split()))
l = 0
r = n - 1
left_sum, right_sum = 0, 0
left_res, right_res = 0, 0
count = 0
# 일종의 투 포인터(Two Pointers) 기법
while l <= r:
# 왼쪽에서 먹을 차례
if count % 2 == 0:
now_sum = 0
while l <= r and now_sum <= right_sum:
now_sum += data[l]
l += 1
left_res += now_sum
left_sum = now_sum
# 오른쪽에서 먹을 차례
elif count % 2 == 1:
now_sum = 0
while l <= r and now_sum <= left_sum:
now_sum += data[r]
r -= 1
right_res += now_sum
right_sum = now_sum
count += 1
print(count, left_res, right_res)
E번 문제: https://codeforces.com/contest/1352/problem/E
n개의 정수로 구성된 수열이 있을 때, 각 n개의 수에 대하여 그 수와 동일한 합을 가지는 '부분 연속 수열'이 존재하는지 찾으면 되는 문제이다.
예를 들어 [3, 1, 4, 1, 5, 9, 2, 6, 5]가 있을 때 6번째 수인 9는 [3, 1, 4, 1]의 합과 같다.
[ 접근 방법 1 ]
일단 이 문제는 투 포인터(Two Pointer)를 이용하여 해결할 수 있다. n개의 수 각각에 대하여 투 포인터 알고리즘을 돌리면 된다. 투 포인터 문제로 유명한 '합이 M인 부분 연속 수열 찾기' 코드를 그대로 쓰면 된다.
단, 이 문제에서는 부분 연속 수열의 길이가 2 이상이 되라고 하였으므로 투 포인터 알고리즘을 길이가 2 이상인 경우만 찾도록 수정해서 이용하면 된다.
코드포스 문제를 풀다 보면, 투 포인터 문제가 굉장히 자주 나오는 것 같다. 혹은... 내가 그냥 해법으로 투 포인터를 먼저 생각해서 그러는 거일 수도 있겠다. 근데 이게 가끔은 시간 초과를 받는 경우도 있으니 조심해야 한다.
for _ in range(int(input())):
n = int(input())
data = list(map(int, input().split()))
result = 0
for x in data:
summary = 0
end = 0
for start in range(n):
while summary < x and end < n:
summary += data[end]
end += 1
if summary == x and end - start >= 2:
result += 1
break
summary -= data[start]
print(result)
근데... 걱정했던 대로 위 코드는 시간초과를 받았다. 투 포인터를 이용할 때에도 사실 O(N^2)의 해법으로 시간 복잡도가 똑같기 때문에 괜찮을 줄 알았는데, 파이썬을 이용하고 있기 때문인지... 시간 초과를 받을 줄은 몰랐다. ㅠㅠ 시간 초과를 받은 케이스를 보니까 정말 간발의 차이로 시간 초과를 받았다. 0.5초만 더 널널했어도, 시간 초과를 받지 않았을 것 같다.
[ 접근 방법 2 ]
아무튼 같은 O(N^2)이지만, 조금 더 빠른 해법은 모든 구간의 합을 하나의 배열에 기록해 놓는 방법이다. (계수 정렬 할 때 처럼) 모든 값들이 n (1 <= n <= 8000) 보다 작기 때문에 이 또한 가능하다. 시간 초과에 걸리지 않는, 정답 코드는 다음과 같다.
[ 정답 코드 ]
for testcase in range(int(input())):
n = int(input())
data = list(map(int, input().split()))
# 모든 구간 합을 저장하기 위한 집합 자료형
visited = set()
# 길이가 2 이상인 모든 구간 합을 집합에 저장
for i in range(n):
summary = data[i]
for j in range(i + 1, n):
summary += data[j]
if summary > n:
break
visited.add(summary)
# 각 값을 확인하며, 계산할 수 있는 구간 합인 경우 카운트
result = 0
for x in data:
if x in visited:
result += 1
print(result)
F번 문제: https://codeforces.com/contest/1352/problem/F
[ 문제 해설 ]
이 문제도 구현 문제인데, 최대한 구현 실수가 발생하지 않게 깔끔한 아이디어로 푸는 것이 중요하다. 일단 가장 중요한 게 n1 = 0인 케이스이다. 이 때는 n0과 n2 둘 중에 하나는 0이 되어야 한다. 안 그러면 조건이 만족되지 않는다. 따라서 n1 = 0인 경우에는, 단순히 n0과 n2 중에 하나만 0이 아닌 값을 가진다는 것을 고려해서 풀면 된다.
그리고 n1 = 0인 케이스가 아니라면, 다음과 같이 먼저 처리해서 문제를 해결할 수 있다.
해결법은 바로 다음과 같다. 먼저 (n2 + 1)의 크기만큼 1을 출력한다. 그리고 n0의 크기만큼 0을 출력한다. 이후에 n1의 크기만큼 010101... 을 반복해서 출력하면 된다. 그러면 정확히 조건을 만족할 수 있다.
[ 정답 코드 ]
for testcase in range(int(input())):
n0, n1, n2 = map(int, input().split())
# n1가 0인 특이 케이스 처리
if n1 == 0:
if n0 > 0:
print("0" * (n0 + 1))
else:
print("1" * (n2 + 1))
continue
# 일반적인 케이스 처리
print("1" * (n2 + 1), end="")
print("0" * n0, end="")
for i in range(n1):
if i % 2 == 0:
print("0", end="")
else:
print("1", end="")
print()
G번 문제: https://codeforces.com/contest/1352/problem/G
[ 문제 해설 ]
이 문제도 간단한 아이디어를 떠올리면 간단히 풀 수 있다. 필자는 대회 당시에는 매우 복잡하게 푼 것 같은데, 실제로는 매우 간단하게도 문제를 해결할 수 있었다.
홀수를 먼저 내림차순으로 출력한 뒤에 4와 2를 출력하고, 다시 모든 짝수를 오름차순으로 차례대로 출력하면 된다. 이렇게 대칭을 이루도록 출력하면 간단하게 해결된다.
예를 들어 n = 11이라고 하면,
[ 11 9 7 5 3 1 ] [ 4 2] [6 8 10]로 출력하면 된다.
위 출력 결과를 보면 인접한 모든 수들은 2 이상, 4 이하로 차이가 난다.
[ 정답 코드 ]
for _ in range(int(input())):
n = int(input())
# 4보다 작은 경우, 만들 수 없음
if n < 4:
print(-1)
continue
# 모든 홀수를 먼저 내림차순으로 출력
for i in range(n, 0, -1):
if i % 2 == 1:
print(i, end=' ')
# 4와 2를 출력
print(4, 2, end=' ')
# 모든 짝수를 오름차순으로 출력
for i in range(6, n + 1, 2):
print(i, end=' ')
print()
'알고리즘 대회' 카테고리의 다른 글
| [코드포스] Codeforces Round #669 (Div. 2) (0) | 2020.09.10 |
|---|---|
| [코드포스] Codeforces Round #639 (Div. 2) (0) | 2020.05.11 |
| 코드포스(Codeforces) 대회에서 소스코드 해킹(Hack) 방법 (0) | 2020.05.10 |
| [코드포스] Codeforces Round #637 (Div. 2) (0) | 2020.04.25 |
| [코드포스] Codeforces Round #634 (Div. 3) (0) | 2020.04.23 |
