[백준 BOJ / Python] 27377번 읽씹 멈춰! Greedy (그리디)
문제 문자를 직접 타이핑하는 방법은 s초, 복사&붙여넣기 방법은 t초가 걸릴 때, 같은 말을 n번 반복해서 입력하는데 걸리는 최소 시간을 구하는 문제이다. 풀이 같은 말이 c번 적혀있고 추가로 c번 작성한다고 한다면 (2배로 만든다면) 위의 그림과 같이 s초씩 c번 작성하는 방법과 t초동안 한 번에 복붙하는 방법이 있다. 즉, 최소 시간을 만들기 위해서는 문자를 두배로 만들 때, 두 가지 방법 중 더 적은 시간을 소요하는 방법을 선택해야 한다. 같은 말을 n번 작성하는데 걸리는 시간을 계산할 때, 작성된 글 맨 마지막부터 그리디 알고리즘 방식으로 생각하면 쉽다. 남은 횟수가 홀수일 경우에는 복붙 방법을 사용할 수 없기 때문에 남은 횟수를 1 줄이고 s초를 더한다. 남은 횟수가 짝수일 경우에는 남은 횟수를..
Study/Coding Test
2023. 2. 18.