이 문제에서는 숫자로 이루어진 target[] 배열이 주어집니다. 모든 요소가 0인 배열 [0,0,0,…]을 아래 두 가지 연산만 사용하여 목표 배열로 변환할 때 필요한 최소 단계 수를 구해야 합니다.
- 증가 연산 — 모든 요소를 1씩 증가시킬 수 있으며, 각 증가 연산은 개별적으로 단계에 포함됩니다. (n개의 요소를 n번 증가시키면 단계 수 = n)
- 배가 연산 — 배열 전체를 한 번에 두 배로 만듭니다. 모든 요소에 대해 한 번만 계산됩니다. (각 배가 연산은 모든 요소의 값을 두 배로 만들며, 단계 수 1로 계산)
목표는 목표 배열에 도달하는 최소 단계 수를 찾는 것입니다. 예를 들어 [0,0,0]은 최소 3단계로 [1,1,1]이 될 수 있고(모든 요소에 증가 연산 적용), 여기에 배가 연산을 한 번 추가하면 [2,2,2]가 되어 총 4단계가 필요합니다(증가 3회 + 배가 1회).
입력 예시 1
target[]= { 1,2,2,3 }
출력
{0,0,0,0}에서 목표 배열까지 도달하는 최소 단계 : 6
풀이 과정
초기 상태는 { 0,0,0,0 }입니다.
증가 연산 3회 → { 0,1,1,1 } // 각 요소별로 개별 증가
배가 연산 1회 → { 0,2,2,2 } // 전체 요소에 배가 적용
증가 연산 2회 → { 1,2,2,3 }
총 단계 = 3 + 1 + 2 = 6
입력 예시 2
target[]= { 3,3,3 }
출력
{0,0,0}에서 목표 배열까지 도달하는 최소 단계 : 7
풀이 과정
초기 상태는 { 0,0,0 }입니다.
증가 연산 3회 → { 1,1,1 } // 각 요소별로 개별 증가
배가 연산 1회 → { 2,2,2 } // 전체 요소에 배가 적용
증가 연산 3회 → { 3,3,3 }
총 단계 = 3 + 1 + 3 = 7
알고리즘 접근 방식
- 정수 배열
target[]은 도달해야 할 목표 값들을 저장합니다. - 함수
minSteps(int target[], int n)은 목표 배열과 그 길이 'n'을 입력으로 받아, 모두 0인 상태에서 목표 배열까지 도달하는 최소 단계 수를 반환합니다. - 변수
count는 단계 수를 저장하며 초기값은 0입니다. - 변수
max는 배열 내 최댓값을 저장하며 초기값은target[0]입니다. - 변수
pos는 최댓값의 인덱스를 저장하며 초기값은 0입니다. - 목표 배열의 모든 요소가 0이라면 단계가 필요 없으므로 0을 반환합니다. (for 반복문으로 0의 개수를 세어 count == n이면 모두 0)
- 이 접근 방식은 목표 배열에서 출발하여 모두 0인 상태로 거꾸로 진행합니다.
- 홀수인 요소에서 1을 빼서 모든 요소를 짝수로 만듭니다. 각 감소마다 count를 1씩 증가시킵니다(증가 연산과 동일하게 계산).
- 이 시점에서 모든 요소는 짝수가 됩니다.
- 같은 루프 안에서 최댓값과 그 위치도 함께 찾아
max와pos를 갱신합니다. - 이후 최댓값이 1이 될 때까지 전체 배열을 2로 나눕니다. 나누는 과정에서 어떤 요소가 홀수가 되면 1을 빼고 count를 증가시키며, 전체 나누기(배가의 역연산)에는 count를 한 번만 증가시킵니다.
- 마지막에는 모든 요소가 0 또는 1이 되므로, 값이 1인 요소들을 0으로 만들면서 count를 다시 증가시킵니다.
- count에 누적된 단계 수를 결과로 반환합니다.
구현 예제
#include <bits/stdc++.h>
using namespace std;
int minSteps(int target[],int n){
int i;
int count=0;
int max=target[0];
int pos=0;
for(i=0;i<n;i++)
if(target[i]==0)
count++;
//모두 0이면 목표와 동일
if(count==n)
return 0;
count=0;
//홀수에서 1을 빼서 모두 짝수로 만듦
for(i=0;i<n;i++){
if(target[i]%2==1){
target[i]=target[i]-1;
count++;
}
//최댓값과 그 위치 탐색
if(target[i]>=max){
max=target[i];
pos=i;
}
}
//모든 요소가 1이 될 때까지 2로 나누고 count 1씩 증가
while(target[pos]!=1){
for(i=0;i<n;i++){
if(target[i]%2==1){
target[i]=target[i]-1;
count++;
}
target[i]=target[i]/2;
}
count++;
}
//배열 전체가 {1}이면 0으로 만들고 count 증가
while(target[pos]!=0){
for(i=0;i<n;i++){
if(target[i]!=0){
target[i]=target[i]-1;
count++;}
}
}
return count;
}
int main(){
int target[]={15,15,15};
cout<<"\nMinimum steps to get the given desired array:"<<minSteps(target,3);
return 0;
}
실행 결과
주어진 원하는 배열을 얻기 위한 최소 단계: 15