[앳코더] AtCoder Beginner Contest #178

대회 링크: atcoder.jp/contests/abc178

A번 문제: atcoder.jp/contests/abc178/tasks/abc178_a

 

  이 문제는 입력으로 1이 들어왔을 때 0을 출력하고, 입력으로 0이 들어왔을 때 1을 출력하면 되는 문제다.

 

[ 문제 해설 ]

 

  단순히 하라는 대로 구현하면 된다.

 

[ 정답 코드 ]

 

x = int(input())
 
if x == 0:
    print(1)
else:
    print(0)

 

B번 문제: atcoder.jp/contests/abc178/tasks/abc178_b

 

  a, b, c, d가 입력으로 들어왔을 때 a <= x <= b와 c <= y <= d가 성립하도록 x랑 y를 하나씩 뽑을 수 있다. 이때 만들 수 있는 x * y 중에서 가장 큰 값이 무엇인지 구하면 되는 문제다.

 

  단, a, b, c, d는 -10억부터 +10억 사이의 정수다.

 

[ 문제 해설 ]

 

  다음의 4가지 경우 중에서 가장 큰 값을 출력하면 된다.

 

  1) a * c

  2) a * d

  3) b * c

  4) b * d

 

[ 정답 코드 ]

 

a, b, c, d = map(int, input().split())
 
print(max(a * c, a * d, b * c, b * d))

 

C번 문제: atcoder.jp/contests/abc178/tasks/abc178_c

 

  길이가 n인 수열 {A1, A2, A3, ..., An}이 있을 때, 다음의 조건을 만족하는 수열의 개수를 세면 되는 문제다.

 

  ▶ 0 <= Ai <= 9

  ▶ 값이 0인 원소가 하나 이상 존재한다.

  ▶ 값이 9인 원소가 하나 이상 존재한다.

 

[ 문제 해설 ]

 

  이 문제는 N이 최대 1,000,000일 수 있으므로 O(N) 안쪽으로 해결해야 한다. 따라서 전형적인 DP를 이용해 문제를 해결할 수 있다.

 

  ▶ DP[n][0]: 길이가 N이면서 조건을 만족하는 수열의 개수 (단, 0의 개수: 0, 9의 개수: 0)

  ▶ DP[n][1]: 길이가 N이면서 조건을 만족하는 수열의 개수 (단, 0의 개수: 1 이상, 9의 개수: 0)

  ▶ DP[n][2]: 길이가 N이면서 조건을 만족하는 수열의 개수 (단, 0의 개수: 0, 9의 개수: 1 이상)

  ▶ DP[n][3]: 길이가 N이면서 조건을 만족하는 수열의 개수 (단, 0의 개수: 1 이상, 9의 개수: 1 이상)

 

  위와 같이 정의하여 해결할 수 있다.

 

  ... 그냥 더 쉽게 수학 공식으로 해결하자.

 

  ▶ 모든 경우의 수: 10^n

  ▶ 9를 제외한 경우의 수: 9^n

  ▶ 0을 제외한 경우의 수: 9^n

  ▶ 0과 9 둘 다 없을 때의 경우의 수: 8^n

 

  따라서 전체 경우의 수는 10^n - 9^n - 9^n + 8^n이다. 이를 포함배제의 원리(Principle of inclusion-exclusion)라고도 한다.

 

[ 정답 코드 ]

 

  참고로 값이 매우 매우 커질 수 있으나 파이썬(Python)의 경우 이를 효과적으로 처리한다.

 

n = int(input())
mod = int(1e9) + 7

result = ((10 ** n) - 2 * (9 ** n) + (8 ** n)) % mod
print(result)

 

D번 문제: atcoder.jp/contests/abc178/tasks/abc178_d

 

  하나의 자연수 S가 있을 때, 다음의 조건을 만족하는 수열의 개수를 구하고자 한다.

 

  ▶ 모든 원소가 3 이상의 정수

  ▶ 모든 원소의 합이 S

 

  예를 들어 S = 7이라고 하면 {7], {3, 4}, {4, 3}이 있으므로 답은 3이다.

 

[ 문제 해설 ]

 

  이 문제는 S가 최대 2,000이므로 이차 시간 안에 동작하는 알고리즘을 고안해야 한다. 또한 최적 부분 구조(Optimal Substructure)가 성립하므로 DP를 이용해 문제를 해결할 수 있다. 예를 들어 S = 7의 모든 경우의 수는 다음의 모든 경우를 고려한 것과같다.

 

  ▶ {7}

  ▶ {3}에 DP[4]의 모든 수열을 이어 붙인 것들

  ▶ {4}에 DP[3]의 모든 수열을 이어 붙인 것들

  ▶ {5}에 DP[2]의 모든 수열을 이어 붙인 것들

  ▶ {6}에 DP[1]의 모든 수열을 이어 붙인 것들

 

  이런 아이디어를 고려하면 다음과 같은 코드로 문제를 해결할 수 있다.

 

[ 정답 코드 ]

 

s = int(input())
d = [0] * 2001

# 일단 기본적인 초기 값들 계산해보기
d[0] = 0
d[1] = 0
d[2] = 0
d[3] = 1 # {3}
d[4] = 1 # {4}
d[5] = 1 # {5}
d[6] = 2 # {6}, {3, 3}
d[7] = 3 # {6}, {3, 4}, {4, 3}
d[8] = 4 # {8}, {3, 5}, {4, 4}, {5, 3}
d[9] = 6 # {9}, {3, 6}, {4, 5}, {5, 4}, {6, 3}, {3, 3, 3}
 
for i in range(10, 2001):
    summary = 1 # 일단 자기 자신 하나를 원소로 삼는 경우
    for j in range(3, i):
        summary += d[i - j]
        summary = summary % (int(1e9) + 7)
    d[i] = summary
 
print(d[s])

 

E번 문제: atcoder.jp/contests/abc178/tasks/abc178_e

 

  2D 공간에 N개의 점(Point)이 존재한다. 이때 맨해튼 거리(Manhattan Distance)가 가장 먼 두 개의 점을 찾는 문제다. 예를 들어 i와 j 두 점이 있으면 맨해튼 거리는 |Xi - Xj| + |Yi - Yj|를 의미한다.

 

[ 문제 해설 ]

 

  먼저 Xi <= Xj라고 했을 때 다음의 두 경우로 나눌 수 있다.

 

  ▶ 만약 Yi <= Yj라면 거리는 (Xj + Yj) - (Xi + Yi)이다.

  ▶ 만약 Yi > Yj라면 거리는 (Xj - Yj) - (Xi - Yi)이다.

 

  이 문제는 잘 알려진 문제로, 맨해튼 거리이기 때문에 이러한 조건이 성립한다. 참고로 맨해튼 거리가 아니라 유클리드 거리라면 컨벡스 헐(Convex Hull)을 활용해야 제한 시간 안에 문제를 해결할 수 있다.

 

  첫 번째 경우를 보면 X + Y만 구하면 된다는 것을 알 수 있다.

  두 번째 경우를 보면 X - Y만 구하면 된다는 것을 알 수 있다.

 

  결과적으로 max(max(x + y) - min(x + y), max(x - y) - min(x - y))를 출력하면 된다.

 

[ 정답 코드 ]

 

n = int(input())
plus = []
minus = []
 
for i in range(n):
    x, y = map(int, input().split())
    plus.append(x + y)
    minus.append(x - y)
 
result = max(max(plus) - min(plus), max(minus) - min(minus))
print(result)