. 아이즈 키보드

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개의 문자를 표시하는 데 필요한 최소 작업 수를 나타냅니다.
   • 화면에 'A' 하나를 표시하는 데 0번의 작업이 필요하므로 dp[1] = 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키 키보드

<?php
// Example usage
echo minOperations(3); // Output: 3
echo minOperations(1); // Output: 0
echo minOperations(10) . "\n"; // Output: 7
echo minOperations(24) . "\n"; // Output: 9
?>

설명:

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

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

연락처 링크

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

이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 . 아이즈 키보드의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!