공부정리

정답 코드 먼저 살펴보자

import sys
n = int(sys.stdin.readline())

two_count = 0
five_count = 0

two = 2 
while two <= n :
  two_count += n // two
  two *= 2

five = 5
while five <= n:
  five_count += n // five
  five *= 5

print(min(two_count, five_count))

팩토리얼을 수행 했을때 0이 몇개 나오는지 반환하는 문제이다

0을 만들수 있는 조건은 2와 5의 곱이다.

우리는 팩토리얼을 구하는 숫자 범위 안에서 2의 개수와 5의 총개수를 비교해주어야 한다.

10을 예로 들어보자

1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10

2의 등장 개수를 구해야 한다. 근데 4에는 2가 두개 있고 8에는 2가 3개 있다.

이진수로 살펴보자

    1   # 1 
  1*2   # 2 
  3*1   # 3 
  2*2   # 4 
  5*1   # 5 
  3*2   # 6 
  7*1   # 7 
2*2*2   # 8 
  9*1   # 9 
  5*2   # 10

나누어 주는 수를 2씩 곱해주면서 위의 식에서 2를 하나씩 제거해준다는 개념으로 접근했다.

2^1에서 1단계의 2들에 접근해 카운팅 해주었고

2^2에서 2단계의 2들에 접근해 카운팅 해주었다

2^3도 마찬가지로 나누어주는 수를 키워주면서 다음 단계의 2에 접근하는식으로 해결하였다.

(머릿속에 있는걸 글로 적으려니까 쉽지 않다. 적은후에 다시 한번 퇴고해봐야겠다)

문제 : https://www.acmicpc.net/problem/1676

기본적인 다이나믹 프로그래밍이다.

배열을 그리고 초반 몇개를 직접 시도해보면 규칙이 보일거다

정답 코드 먼저 보자

n, k = map(int, input().split())

dp = [[0] * (k+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(0, n+1) :
  for j in range(1, k+1) :
    dp[i][j] = dp[i-1][j] + dp[i][j-1]

print(dp[n][k] % 1000000000)

k = 1 인경우 모든 숫자는 1이다.

k = 2 인경우 모든 숫자는 (n+1)을 가진다.  n=2: (0,2)(1,1)(2,0)   n=3: (0,3)(1,2)(2,1)(3,0)   n=4: (0,4)(1,3)(2,2)(3,1)(4,0)

k= 3 인경우 모든 숫자는 k=2,n=n 일때와 k=3,n=n-1일때의 경우의수의 합이다. n=2: (0,0,2)(0,2,0)(2,0,0)(1,1,0)(1,0,1)(0,1,1)

k= i 인경우 모든 숫자는 k=i-1,n=n 일때와 k=i,n=n-1일때의 합이다 dp[i][j] = dp[i-1][j] + dp[i][j-1]

n = 1 인경우 k의 숫자와 같은 값을 가진다. k=2: (0,1)(1,0)   k=3: (0,0,1)(0,1,0)(1,0,0)  k=4: (0,0,0,1)(0,0,1,0)(0,1,0,0)(1,0,0,0)

문제 :  https://www.acmicpc.net/problem/2225

이 문제는 크로아티에서 고등학생 대상으로 나온 문제다.

상당히 애를 먹었던 문제다.(아직 멀었나 보다)

코드 먼저 살펴보자

a,b = map(int, input().split())

def calc(number) :
  if number == 0 :
    return 0
  elif number == 1 :
    return 1 
  elif number % 2 == 0 :
    return number // 2 + 2 * calc(number // 2)
  elif number % 2 == 1 :
    return number // 2 + 2 * calc(number // 2) + 1

print(calc(b) - calc(a-1))

애를 먹었던 거에 비해서는 굉장히 간단하다. 

규칙만 잘 찾으면 절대 어렵지 않은 문제다.

그 규칙에 대해서 아래 필기로 같이 살펴보자

1. f(홀수)는 무조건 1이다
2. f(짝수)는 f(짝수/2)의 2배다 (f(2) == 2, f(4) == 4, f(6) == 2 * f(3))
3. 입력받은 a에서 b까지의 각 숫자들을 나눌수 있는 숫자들중 2의 거듭제곱에 해당하는 가장 큰수 들의 합이다. 
   (숫자의 범위들을 살펴보자 0 <= a, b <= 10^15 => 순회 잘못걸리면 2초안에 못들어온다) => 범위를 탐색하는 것이 아니다.
4. s(n)은 f(1) + f(2) + .... + f(n-1) + f(n) 의 값이다. 3번의 정의를 s(b) - s(a-1)로 바꾸면??? => 문제에서 요구하는 것과 같다.
5. n이 짝수면 s(n)의 절반은 1이다(절반은 홀수니까), n이 홀수면 s(n)의 절반 + 1 은 1이다
6. 절반의 1을 뺀 나머지는 전부 짝수다 f(2n) = 2 * f(n)이므로 점화식 설명 내용 이미지의 그림 처럼 짝수들만 더한 값은 
   f(2) + f(4) + f(6) + ..... +  f(2n-2) + f(2n) = 2f(1) + 2f(2) + 2f(3) + ..... + 2f(n-1) + 2f(n) = 2s(n) 이다
7. n이 짝수 s(n) = n / 2 + s(n/2),  n이 홀수 s(n) = n / 2 + s(n/2) + 1 이 되게 된다.
8. 7번의 내용을 재귀함수로 만들면 끝!

출처: https://www.acmicpc.net/problem/1407

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

1년 전에 풀때 못풀었던 문제다. 

이번에 풀게되었는데 이번에도 실패다. (고마워요 다른 블로거 포스팅들) 다음엔 꼭 성공하리...

다음에 실패하지 않기 위해 이번에는 생각을 정리해서 글을 남겨둘 거다.

다음에 풀 나에게 힌트가 되기를 바라며...

정답 코드 먼저!!!

n = input()
first = list(input())
target = list(input())

def change_zero_index(light) :
  count = 1
  light[0] = str(1 - int(light[0]))
  light[1] = str(1 - int(light[1]))

  for i in range(1, len(light)) :
    if target[i-1] != light[i-1] :
      count += 1
      light[i-1] = str(1 - int(light[i-1]))
      light[i] = str(1 - int(light[i]))
      if i != int(n) - 1 :
        light[i+1] = str(1 - int(light[i+1]))

  if light == target:
      return count

  
  return 100001

def not_change_zero_index(light) :
  count = 0
  
  for i in range(1, len(light)):
    if target[i-1] != light[i-1]:
      count += 1
      light[i-1] = str(1 - int(light[i-1]))
      light[i] = str(1 - int(light[i]))

      if i != int(n) - 1:
        light[i+1] = str(1 - int(light[i+1]))

  if light == target:
      return count

  return 100001

answer_first = change_zero_index(first[:])
answer_second = not_change_zero_index(first[:])
answer = min(answer_first, answer_second)

if answer == 100001 :
  print(-1)
else :
  print(answer)

접근방법 

1. 첫번째 전구를 토글하고 접근하는 것과 토글하지 않고 접근하는 경우로 케이스를 나눠서 계산한다. 
   => 첫번째 전구는 비교할 이전의 전구 상태가 존재하지 않는다. 그래서 두개의 경우로 나누어서 접근
2. 순회하면서 이전의 전구 상태와 바꿔야 하는 상태를 비교하고 토글여부를 결정한다.
   =>  이전 전구의 상태를 비교하면서 순회하면 결국 현재 전구도 비교하게 될 것이다.
3. 이전에 지나온 전구는 건드리지 않는다.
   => 이전의 전구를 건드리면 다시 그 이전으로 돌아가야 하고 이렇게 되면 제일 처음의 과정을 반복하게 된다. 메모리 초과나 시간 초과에 걸릴 것이다.

(대체 이런개념을 제한 시간안에 어떻게 떠올리는거지....)

메모리 초과로 실패했던 이전의 코드

def toggle_item(x) :
  if x == '1' :
    return '0'
  return '1'

def toggle(s, i) :
  s = list(s)
  
  if i == 0 :
    s[:2] = list(map(toggle_item, s[:2]))
  elif i == len(s) :
    s[i-2:] = list(map(toggle_item, s[i-2:]))
  else :
    s[i-1:i+2] = list(map(toggle_item, s[i-1:i+2]))
  return ''.join(s) 

n = input()
first = input()
second = input()

# bfs
bfs = []
result_list = {}
result_list[first] = 0
bfs.append([first, 0])

while True :
  if len(bfs) == 0:
    break
  
  target, count = bfs.pop(0)
  
  if target == second :
    break
  for i in range(len(target)) :
    toggle_target = toggle(target, i)
    if toggle_target in result_list :
      result_list[toggle_target] = min(result_list[toggle_target], count+1)
    else :
      result_list[toggle_target] = count+1
    bfs.append([toggle_target, count+1])

if second in result_list :
  print(result_list[second])
else :
  print(-1)

bfs로 접근하려 했었고 테스트 케이스만 통과했었고 반례 넣어보면서 탈출조건을 세부화 하려 했으나 메모리 초과로 실패해버렸다.