A. Single Push

문제

https://drive.google.com/open?id=1ZcxxImU46U4PYR1_soSgOPuTQX7OiQcl

예시

[input]
4
6
3 7 1 4 1 2
3 7 3 6 3 2
5
1 1 1 1 1
1 2 1 3 1
2
42 42
42 42
1
7
6

[output]
YES
NO
YES
NO

답1 – 이곳을 클릭하면 정답이 보입니다
def answer(a, b) :
  startDiff = -1
  diff = 0
  theEnd = False
  for i in range(len(a)) :
    diff = b[i] - a[i]
    if diff < 0 :
      return "NO"
    if diff > 0 :
      if theEnd is True :
        return "NO"
      if startDiff == -1 :
        startDiff = diff
      if startDiff != -1 :
        if diff != startDiff :
          return "NO"
    if startDiff != -1 :
      if diff == 0 :
        theEnd = True
  return "YES"

testCount = int(input())
for _ in range(testCount) :
  n = input()
  a = list(map(int, input().split()))
  b = list(map(int, input().split()))
  print(answer(a, b))
답2 – 이곳을 클릭하면 정답이 보입니다

설명

B. Silly Mistake

문제

https://drive.google.com/open?id=1k2W73uXVuUsgZXgcpLhcCwH_7EbHfqo3

예시

[input]
6
1 7 -7 3 -1 -3

[output]
1
6

[input]
8
1 -1 1 2 -1 -2 3 -3

[output]
2
2 6

[input]
6
2 5 -5 5 -5 -2

[output]
-1

[input]
3
-8 1 1

[output]
-1

답1 – 여기를 클릭하면 정답이 보입니다
def answer(arr) :
  n = len(arr)
  if n%2 != 0 : return -1
  if sum(arr) != 0 : return -1
  
  plusCount, minusCount, groupCount = (0, 0, 1)
  partitions = [0]
  history = {}
  i = 0
  while(i != n) :
    e = arr[i]
    if e > 0 :
      if i == n-1 : return -1
      plusCount += 1
      if plusCount*2 > n : return -1
      if history.get(e) is None : history[e] = 0
      else : return -1
      history[e] += 1
    else :
      minusCount += 1
      if minusCount*2 > n : return -1
      if history.get(-e) is None or history[-e] == 0 : return -1
      history[-e] -= 1
      if (i+1)%2 == 0 and i != n-1 :
        clear = True
        for k, v in history.items() :
          if v > 0 :
            clear = False
            break
        if clear is True :
          partitions.append(i+1)
          groupCount += 1
          history = {}
    i += 1

  _p = [0]*len(partitions)
  for i in range(1, len(partitions)) :
    _p[i-1] = str(partitions[i] - partitions[i-1])
  _p[-1] = str(n - partitions[-1])
  return (str(groupCount) + "\n" + " ".join(_p))


n = input()
arr = list(map(int, input().split()))
print(answer(arr))

잘 작동은 하지만, TMI다. 너무 코드가 길고 복잡해!

답2 – 여기를 클릭하면 정답이 보입니다
def answer(arr) :
  s1 = set()
  s2 = set()
  ans = []
  for e in arr :
    if e > 0 :
      # 지금 들어오는 숫자가 이미 들어와있으면 아니되옵니다!
      if (e in s1) or (e in s2) :
        return -1
      s1.add(e)
    else :
      e = -e
      if (e not in s1) :
        print(-1)
      s1.remove(e) # 음수가 들어왔으니까 자기 짝을 찾아서 지워준다
      s2.add(e) # 여기에는 왜 더하는거지? 나중에 그룹에 몇개있는지 계산할때 쓰인다.
    if len(s1) == 0 : # 짝이 다 맞아서 남는게 없다면.. (그룹을 만들어줘야겠지!)
      ans.append(len(s2)*2)
      s2.clear() # 깨끗이 기록을 삭제해서 다음 그룹만들때 쓴다.
      
n = input()
arr = list(map(int, input().split()))
print(answer(arr))

set을 이용해서 개깔끔하게 풀었다!

C. Sweets Eating

문제

https://drive.google.com/open?id=1Xn5DLmgseRjAzuopnwV-WUpH1Ea4z0-z

예시

[input]
9 2
6 19 3 4 4 2 6 7 8

[output]
2 5 11 18 30 43 62 83 121

[input]
1 1
7

[output]
7

답1 – 여기를 클릭하면 정답이 보입니다
import math

def answer(n, m, sweets) :
  panalties = []
  sweets.sort(reverse=True)
  for i in range(n, 0, -1) :
    maxDay = math.ceil(i/m)
    panalty = 0
    k = n - i
    for j in range(1, maxDay+1) :
      if j == maxDay :
        panalty += sum(sweets[k:]) * j
      else :
        panalty += sum(sweets[k:k+m]) * j
        k += m
    panalties.append(panalty)
  return " ".join([str(panalties[i]) for i in range(len(panalties)-1, -1, -1)])

n, m = map(int, input().split())
sweets = list(map(int, input().split()))
print(answer(n, m, sweets))

직관적이기는 한데, 너무 느리다

답2 – 여기를 클릭하면 정답이 보입니다
def answer(n, m, sweets) :
  sweets.sort()
  panalties = []
  d = [0]*n
  s = 0
  for i in range(n) :
    d[i%m] += sweets[i]
    s = s+d[i%m]
    panalties.append(s)
  return " ".join([str(p) for p in panalties])

n, m = map(int, input().split())
sweets = list(map(int, input().split()))
print(answer(n, m, sweets))

위 그림처럼 생각하면 안되고, 아래처럼 생각해야한다.

추가된숫자들을 담는 배열(d)을 만들 생각은 어떻게 한걸까?

잘 보면, 4개 -> 5개로 갈때 1하고 3의 day가 1씩 업그레이드 되면서 각각 한번씩 더 더해진다. 즉! 이런식으로 day가 늘어날때 증가되는 놈들의 세트가 i%m개 있고, 이거를 저장해놔야 stack처럼 계속 늘릴 수 있기 때문에 d배열이 필요한거다. 지금은 하루에 먹을 수 있는 총량(m)이 2니까 배열의 size가 2이지만, m = 3, 4, 5가 되면 size도 3, 4, 5가 되야한다.

와,, 그러니까 이 문제는… 숫자를 하나씩 집어 넣으면서 그 변화 과정을 살펴봐야 하는거였어. 약간 점화식 3.5점짜리 문제같다. 아주 좋은걸 배웠다!! 움직임(변화과정)!!