A. Divisibility Problem

문제

예시

[input]
5
10 4
13 9
100 13
123 456
92 46

[output]
2
5
4
333
0

답1 – 이곳을 클릭하면 정답이 보입니다
def answer(a, b) :
  if a%b == 0 :
    return 0
  return (((a//b)+1) * b) - a

testCount = int(input())
for _ in range(testCount) :
  a, b = map(int, input().split())
  print(answer(a, b))

하나씩 증가시키면서 계속 나눠볼 필요는 없고, 그 a보다 큰 b의 배수중 가장 작은놈이랑 b랑 뺀 그 차이값만큼만 움직여주면된다.

답2 – 이곳을 클릭하면 정답이 보입니다

설명

B. K-th Beautiful String

문제

예시

[input]
7
5 1
5 2
5 8
5 10
3 1
3 2
20 100

[output]
aaabb
aabab
baaba
bbaaa
abb
bab
aaaaabaaaaabaaaaaaaa

답1 – 여기를 클릭하면 정답이 보입니다
def answer(n, k) :
  m = 1
  while(True) :
    if m*(m+1) == 2*k :
      break
    if m*(m+1) > 2*k :
      break
    m += 1
  arr = ['b'] + (['a']*(m))
  startPoint = int(m*(m-1)/2) + 1
  diff = k - startPoint
  arr[(len(arr)-1)-diff] = 'b'
  ab = 'a'*(n-len(arr)) + "".join(arr)
  return ab

testCount = int(input())
for _ in range(testCount) :
  n, k = map(int, input().split())
  print(answer(n, k))

위 이미지처럼 aaabb를 2진수로 11로 표현하고, 2자리(11) -> 3자리(101) -> 4자리(1001) 이렇게 자리수별로 1구간 2구간 3구간…으로 정의한다. 그랬을때 8은 4구간에 있는데, 이거를 구하는 방법은 저 코드의 while문이다.

구간을 구했으면 [‘b’, ‘a’, ‘a’, ‘a’, ‘a’] 배열([1, 0, 0, 0, 0])을 만들고 k(8) 에서 4구간의 시작포인트(7) 를 뺀만큼의 값을 뒤에서 부터해서 1을 넣는다. 그러면 8-7 = 1이니까 뒤에서 한칸 왼쪽에 ‘b’을 넣는다. 이제 이 배열을 string으로 바꿔서 리턴하면 된다. 코드는 퍼포먼스 향상을 위해 이부분을 약간 꼬와놨는데, 개념은 이렇다.

답2 – 여기를 클릭하면 정답이 보입니다

설명

C. Ternary XOR

문제

예시

[input]
4
5
22222
5
21211
1
2
9
220222021

[output]
11111
11111
11000
10211
1
1
110111011
110111010

답1 – 여기를 클릭하면 정답이 보입니다
def answer(x) :
  tieAGun = None
  a = [1]+[0]*(len(x)-1)
  b = [1]+[0]*(len(x)-1)
  ab = [a, b]
  for i in range(1, len(x)) :
    if tieAGun is None :
      if x[i] == 2 :
        a[i] = 1
        b[i] = 1
      if x[i] == 1 :
        tieAGun = 0
        a[i] = 1
    else :
      ab[1-tieAGun][i] = x[i]
  return "".join([str(i) for i in a]) + "\n" + "".join([str(i) for i in b])

testCount = int(input())
for _ in range(testCount) :
  n = input()
  x = input().rstrip()
  print(answer([int(i) for i in x]))

x가 모두 2인 경우에는 어느 한쪽도 2를 줘버리면 최대값이 커져버리기 때문에, 양쪽에 모두 1을 공평하게 준다.

x가 21211 이런식으로 1과 2가 섞여있다면 a가 총대를 매고 큰거 하나 (어쩔수없이)가져간다음에 남은 모든거를 b에 주면된다. 예를들어서, 21211 같은 경우에는 a에게 1을 주고 뒤에 211은 b에게 다 주면 그나마 a가 (b보다는 큰놈이긴 하지만) 작아진다.

답2 – 여기를 클릭하면 정답이 보입니다

설명