99클럽 코테 스터디 17일차 TIL / 그리디

✏️ 문제

[백준/BOJ] 31926번: 밤양갱(https://www.acmicpc.net/problem/31926)

 

달디달고, 달디달고, 달디단, 밤양갱, 밤양갱

<장기하, 밤양갱, 2024>

 

민우는 비비의 신곡 <밤양갱>에 꽂혀 하루 종일 "달디달고 달디달고 달디달고... 달디단"이 머릿속을 맴돌고 있다.

민우의 머릿속에선 daldidalgo가 총 N번 반복된 후, 반복이 완료되었다면 daldidan으로 끝나게 된다. 예를 들어 N=3이라면 민우의 머릿속엔 daldidalgodaldidalgodaldidalgodaldidan이 재생된다.

민우는 N이 주어지면 얼마나 빨리 daldidalgodaldidalgo...daldidan을 컴퓨터에 입력할 수 있는지 궁금하다. 매초 민우는 두 개의 작업 중 하나를 선택하여 시행할 수 있다.

 

• 알파벳 소문자 a부터 z 중에서 민우가 원하는 알파벳을 하나 골라서 지금까지 입력한 내용의 맨 뒤에 입력한다.
• 지금까지 입력한 문자열의 연속된 부분 문자열을 복사 후 입력한 내용의 맨 뒤에 붙여넣는다. 예를 들어 지금까지 작성한 문자열이 ajouapcshake라면, ajouapcshake를 복사할 수도, apc를 복사할 수도 있지만, aashake를 복사하여 붙여넣을 수는 없다.

 

민우는 몇 초 만에 머릿속에 떠오른 가사를 컴퓨터에 입력할 수 있을까?

 

🤖 입출력 예시

 

🧐 난이도/소요 시간

✅ 난이도: solved.ac 기준 S1

✅ 소요 시간: 1시간 30분

✅ 권장 시간: 1시간 15분

 

시간 안에 못 푼 게 굉장히 오랜만이다. 어 실력이 좀 는건가? 싶은 거만한 생각이 들락말락 할 때 쯤 시기적절하게 나타나준 문제다.

 

💡 풀이

1) 문제 유형 파악

최근 그리디 문제가 자주 출제되기도 했고 '최소' 횟수를 구해야 하는 걸 보고 그리디 유형이겠다 싶었다.

 

사실 그리디 유형은 아직 잘 모르겠다. 개인적인 경험으로는 '그리디 문제니까 어떻게 풀어야지'라기보다 '이렇게 풀면 될 것 같은데?' 하고 푼 후 알고리즘 분류를 보면 그리디로 돼있는 경우가 많았다.

---

 

문제의 요구사항

- N개의 daldidalgo와 하나의 daldidan으로 이루어진 가사를 만드는 데 드는 최소 시간 구하기

 

왜 그리디인지? (⚠️ 개인의 생각을 정리한 거라 정확하지 않음)

- 거스름돈 문제에서 동전을 최소한으로 써서 거슬러주려면 금액이 큰 동전을 많이 써야 하듯이 이 문제에서는 길이가 긴 가사를 많이 써야 시간을 단축할 수 있음

→ 이 부분이 그리디적 사고와 관련 있다고 판단

 

2) 아이디어 흐름

① 패턴 찾아보기 - 첫 번째 시도

가장 먼저 시도한 방법은 N=1부터 N=4까지 가사가 만들어지는 과정을 일일이 적어보는 것이었다. 근데 아무래도 손으로 쓰다 보니 휴먼 에러가 있어서 애초에 잘못된 패턴이었는데 이 때는 깔끔하게 정의되는 패턴이라고 생각했다.

 

물론? 제출 결과는 오답.

 

# 첫 번째 오답 코드

import sys

input = sys.stdin.readline

N = int(input())

print(10+(N-1))

 

 

② 패턴 찾아보기 - 두 번째 시도

조금 더 심혈을 기울여 시간을 계산해봤다.

 

N = 1: d/a/l/d/i/dal/g/o (8초) daldida (9초) n (10초)

N = 2: d/a/l/d/i/dal/g/o (8초) daldidalgo (9초) daldida (10초) n (11초)

N = 3: d/a/l/d/i/dal/g/o (8초) daldidalgo (9초) daldidalgodaldida (10초) n (11초)

N = 4: 위와 같은 방법으로 계산했을 때 최종적으로 (12초)

 

여기까지만 적어 보고 '아 달디달고가 한 개일 때 10초고 그 뒤부터는 N을 2로 나눈 몫을 더해주면 되는구나' 했는데 코드 제출하니까 또 오답이었다.

 

# 두 번째 오답 코드

import sys

input = sys.stdin.readline

N = int(input())

print(10+(N//2))

 

이 때부터 너무 단순하게 생각하고 있나? 싶어 논리적인 풀이를 고민해봤다. 이 과정에서 풀이 시간의 대부분이 소요됐다.

 

③ ⭐ '×2' 개념 활용하기 ⭐

완전한 daldidalgo를 하나 만든 것에서부터 출발한다. N이 2 이상일 때 한 개의 daldidalgo가 만들어지고 난 후에는 계속 저걸 복사해서 쓰면 되기 때문이다.

 

daldidalgo가 하나만 완성되고 나면 이제 복사-붙여넣기 과정을 통해 아래처럼 daldidalgo의 개수를 2배씩 증가시킬 수 있다.

 

daldidalgo → 전체 복사-붙여넣기(1초 소요) → daldidalgo daldidalgo

daldidalgo daldidalgo → 전체 복사-붙여넣기(1초 소요) → daldidalgo daldidalgo daldidalgo daldidalgo

 

전체 복사-붙여넣기 과정을 통해 daldidalgo 개수를 2배씩 늘릴 수 있는지 확인하면서 시간은 계속 1초씩 더해주면 되는데 이 부분은 while문을 이용해 구현할 수 있다.

 

while문을 다 돌고 나면 'daldidalgodaldidan'을 만드는 데 필요한 10초를 더해서 최종 값을 출력한다. 

 

설명이 내가 봐도 깔끔하진 않은데 여기까지가 오늘의 최선이라 TIL은 일단 업로드,,

 

3) 구현

import sys

input = sys.stdin.readline

N = int(input())

if N <= 2:
    answer = 10+(N-1)
else:
    cnt = 1 # 8초 동안 다 만들어진 달디달고
    
    sec = 0
    
    while N >= cnt*2:
        sec += 1
        cnt *= 2
    
    answer = 10+sec

print(answer)

 

4) 어려웠던 점/배운 점

🚨 어려웠던 점

• 문제를 이해하는 데에는 오래 걸리지 않았는데 두 번의 틀렸습니다를 만난 후부터는 손으로 쓰면서 생각하는데도 뭔가 계속 헷갈려서 방법을 떠올리는 게 쉽지 않았다.

❗ 배운 점

• 그리디는 쉽지 않다...ㄹ디달고달디달고×∞