650. 2키 키보드

난이도: 중간

주제: 수학, 동적 프로그래밍

메모장 화면에는 'A'라는 글자가 딱 한 개 있습니다. 각 단계마다 이 메모장에서 두 가지 작업 중 하나를 수행할 수 있습니다.

• 모두 복사: 화면에 나타나는 모든 문자를 복사할 수 있습니다. (부분 복사는 허용되지 않습니다.)
• 붙여넣기: 지난번에 복사한 문자를 붙여넣을 수 있습니다.

정수 n이 주어지면 문자 'A'를 화면에 정확히 n번 가져오기 위한 최소 작업 수를 반환합니다.

예 1:

• 입력: n = 3
• 출력: 3
• 설명: 처음에는 문자 'A'가 하나 있습니다.
  • 1단계에서는 모두 복사 작업을 사용합니다.
  • 2단계에서는 붙여넣기 작업을 사용하여 'AA'를 얻습니다.
  • 3단계에서는 붙여넣기 작업을 사용하여 'AAA'를 가져옵니다.

예 2:

• 입력: n = 1
• 출력: 0

예 3:

• 입력: n = 10
• 출력: 7

예 2:

• 입력: n = 24
• 출력: 9

제약조건:

• 1

힌트:

1. n = 3인 경우 마지막 단계에서 클립보드에 몇 개의 문자가 있을 수 있습니까? n = 7? n = 10? n = 24?

해결책:

화면에 정확히 n개의 문자 'A'를 표시하려면 최소 작업 수를 찾아야 합니다. 이를 달성하기 위해 동적 프로그래밍 접근 방식을 사용할 것입니다.

1. 문제 이해:

   • 화면에 하나의 'A'로 시작합니다.
   • "모두 복사"(현재 화면 내용 복사) 또는 "붙여넣기"(마지막 복사한 내용 붙여넣기)를 수행할 수 있습니다.
   • 화면에 정확히 n개의 문자 'A'를 표시하는 데 필요한 최소 작업을 결정해야 합니다.

2. 동적 프로그래밍 접근 방식:

   • DP(동적 프로그래밍) 배열 dp를 사용합니다. 여기서 dp[i]는 화면에 정확히 i개의 문자를 표시하는 데 필요한 최소 작업 수를 나타냅니다.
   • dp[1] = 0으로 초기화하세요. 화면에 'A' 하나를 표시하는 데 0번의 작업이 필요하기 때문입니다.
   • 2부터 n까지의 각 문자 i에 대해 i의 모든 약수를 확인하여 최소 연산을 계산합니다. i가 d로 나누어지면:
     • i에 도달하는 데 필요한 작업 수는 d에 도달하는 작업과 i를 얻기 위해 d를 곱하는 데 필요한 작업의 합입니다.

3. 해결 단계:

   • dp[1]을 제외한 모든 값에 대해 INF(또는 큰 숫자)를 사용하여 DP 배열을 초기화합니다.
   • 2에서 n까지의 각 i에 대해 i의 가능한 제수를 반복하고 복사 및 붙여넣기를 통해 i에 도달하는 데 필요한 작업을 기반으로 dp[i]를 업데이트합니다.

이 솔루션을 PHP로 구현해 보겠습니다: 650. 2키 키보드

설명:

• 초기화: dp는 초기에 도달할 수 없는 상태를 나타내기 위해 큰 숫자(PHP_INT_MAX)로 초기화됩니다.
• 제수 확인: 각 숫자 i에 대해 모든 약수를 확인합니다. d. d에 도달하는 데 필요한 작업을 고려한 다음 곱하여 i를 얻음으로써 dp[i]를 업데이트합니다.
• 출력: 결과는 dp[n] 값이며, 이는 화면에 정확히 n개의 문자를 표시하는 데 필요한 최소 작업을 제공합니다.

이 접근 방식을 사용하면 주어진 제약 조건에 대해 최소 작업을 효율적으로 계산할 수 있습니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이와 같이 더 유용한 콘텐츠를 원하시면 언제든지 저를 팔로우하세요.

• 링크드인
• GitHub