99클럽 코테 스터디 17일차 TIL - 그리디 (백준31926 - 밤양갱)

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

• 오늘의 학습 키워드 : 그리디
• 문제 설명

N=2	8번 : d, a, l, d, i, dal, g, o 9번 : d, a, l, d, i, dal, g, o, daldidalgo 10번 : d, a, l, d, i, dal, g, o, daldidalgo, daldida 11번 : d, a, l, d, i, dal, g, o, daldidalgo, daldida, n
N=3	8번 : d, a, l, d, i, dal, g, o 9번 : d, a, l, d, i, dal, g, o, daldidalgo 10번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgodaldida 11번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgodaldida,n
N=4	8번 : d, a, l, d, i, dal, g, o 9번 : d, a, l, d, i, dal, g, o, daldidalgo 10번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgodaldidalgo, 11번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgodaldidalgo, daldida 12번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgodaldidalgo, daldida,n
N=5	8번 : d, a, l, d, i, dal, g, o 9번 : d, a, l, d, i, dal, g, o, daldidalgo 10번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgodaldidalgo 11번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgodaldidalgo, daldidalgodaldida 12번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgodaldidalgo, daldidalgodaldida, n
N= 6	8번 : d, a, l, d, i, dal, g, o 9번 : d, a, l, d, i, dal, g, o, daldidalgo 10번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgodaldidalgo, 11번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgodaldidalgo, daldidalgodaldidalgodaldida 12번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgodaldidalgo, daldidalgodaldidalgodaldida, n
N= 7	8번 : d, a, l, d, i, dal, g, o 9번 : d, a, l, d, i, dal, g, o, daldidalgo 10번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgodaldidalgo, 11번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgodaldidalgo, daldidalgodaldidalgodaldidalgodaldida 12번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgodaldidalgo, daldidalgodaldidalgodaldidalgodaldida, n
N=8	8번 : d, a, l, d, i, dal, g, o 9번 : d, a, l, d, i, dal, g, o, daldidalgo 10번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgodaldidalgo, 11번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgodaldidalgo, daldidalgodaldidalgodaldidalgodaldidalgo 12번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgodaldidalgo, daldidalgodaldidalgodaldidalgodaldidalgo, daldida 13번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgodaldidalgo, daldidalgodaldidalgodaldidalgodaldidalgo, daldida,n

결론 : N이 2의 거듭제곱일 때마다 시간(또는 횟수)이 1씩 더해집니다
왜냐하면, N =7 -> 마지막에 daldidalgodaldidalgodaldidalgodaldida 와 같이 4개의 반복이 완료되며 더 이상 길게 늘릴 수 없기 때문
따라서 N=8부터는 daldida가 따로 추가

• 공부한 내용 
  

  import sys
  import math
  
  N = int(sys.stdin.readline().strip())
  
  # N이 몇 번의 복사 및 붙여넣기 작업이 필요한지를 계산하기 위해 log2(N)을 사용
  # math.log2(N)은 N이 2의 거듭제곱일 때, 필요한 최소 복사 횟수를 구하는 데 유용
  # 여기에 'daldidalgo'의 첫 문자열 길이 10을 더하여 총 작업 시간을 계산
  print(int(math.log2(N))+10)

• 오늘의 회고
  • 항상 느끼지만 알고리즘 문제를 풀 때마다 초등학교 때의 올림피아드 문제처럼 창의적이고 규칙을 찾아야 하는 느낌이랄까?
    그래서 좀만 더 쓰다보면 먼가 규칙이 나오는것 같다.
  • 물론 규칙을 찾을 때 잘 찾아야한다는거..? 실수하면 안된다는거?
  • 첨에는 3일 때, 
    8번 : d, a, l, d, i, dal, g, o
    9번 : d, a, l, d, i, dal, g, o, daldidalgo
    10번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgo,
    11번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgo, daldida,
    12번 : d, a, l, d, i, dal, g, o, daldidalgo, daldidalgo, daldida,n
    이렇게 생각해서 12번이라고 생각하는 실수를 해서 math.log2(N)에 올림을 적용해서 틀렸다. 이런 실수가 없게 정확하게 찾는게 중요하다 ?