![. eys Keyboard](https://img.php.cn/upload/article/000/000/000/172410864672437.jpg)
650. 2키 키보드
난이도:보통
주제:수학, 동적 프로그래밍
메모장 화면에는 'A'라는 글자가 딱 한 개 있습니다. 각 단계마다 이 메모장에서 두 가지 작업 중 하나를 수행할 수 있습니다.
- 전체 복사: 화면에 있는 모든 문자를 복사할 수 있습니다. (부분 복사는 허용되지 않습니다.)
- 붙여넣기: 지난번에 복사한 문자를 붙여넣을 수 있습니다.
정수 n이 주어지면문자 'A'를 화면에 정확히 n번 가져오기 위한 최소 연산 횟수를 반환합니다.
예 1:
- 입력:n = 3
- 출력:3
- 설명:처음에는 문자 'A'가 하나 있습니다.
- 1단계에서는 모두 복사 작업을 사용합니다.
- 2단계에서는 붙여넣기 작업을 사용하여 'AA'를 얻습니다.
- 3단계에서는 붙여넣기 작업을 사용하여 'AAA'를 얻습니다.
예 2:
예 3:
예 2:
제약조건:
힌트:
- n = 3인 경우 마지막 단계에서 클립보드에 몇 개의 문자가 있을 수 있나요? n = 7? n = 10? n=24?
해결책:
화면에 정확히 n개의 문자 'A'를 표시하려면 최소 작업 수를 찾아야 합니다. 이를 달성하기 위해 동적 프로그래밍 접근 방식을 사용할 것입니다.
문제 이해:
- 화면에 'A' 하나로 시작합니다.
- "모두 복사"(현재 화면 내용 복사) 또는 "붙여넣기"(마지막 복사한 내용 붙여넣기)를 수행할 수 있습니다.
- 화면에 정확히 n개의 문자 'A'를 표시하는 데 필요한 최소 작업을 결정해야 합니다.
동적 프로그래밍 접근 방식:
- DP(동적 프로그래밍) 배열 dp를 사용하세요. 여기서 dp[i]는 화면에 정확히 i개의 문자를 표시하는 데 필요한 최소 작업 수를 나타냅니다.
- 화면에 'A' 하나를 표시하려면 0번의 작업이 필요하므로 dp[1] = 0으로 초기화하세요.
- 2부터 n까지의 각 문자 i에 대해 i의 모든 약수를 확인하여 최소 연산을 계산합니다. i가 d로 나누어지면:
- i에 도달하는 데 필요한 연산 수는 d에 도달하는 연산과 i를 얻기 위해 d를 곱하는 데 필요한 연산의 합입니다.
해결 단계:
- 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에서저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 당신의 지원은 나에게 큰 의미가 될 것입니다!
이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요:
위 내용은 . 아이즈 키보드의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!