[BOJ] 두 배 더하기 12931번 C++

2024. 9. 20. 15:29· Algorithm

 

 

문제

모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다.

  • 배열에 있는 값 하나를 1 증가시킨다.
  • 배열에 있는 모든 값을 두 배 시킨다.

배열 B가 주어졌을 때, 배열 A를 B로 만들기 위한 연산의 최소 횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 N이 주어진다. (1 ≤ N ≤ 50)

둘째 줄에는 배열 B에 들어있는 원소가 공백으로 구분해서 주어진다. 배열에 B에 들어있는 값은 0보다 크거나 같고, 1,000보다 작거나 같다.

출력

첫째 줄에 배열 A를 B로 바꾸기 위한 최소 연산 횟수를 출력한다.

 

접근 방식

 

의외로 간단하게 풀 수 있다.

입력으로 받은 배열을 역으로 2로 나누거나 1을 빼서 0으로 만드는 횟수를 구하면된다.

이때, 만약 한 원소의 값이 홀수라면 1을 증가시킨것이기 때문에 카운트를 따로 세어주면 된다.

 

즉, 예를 들어 배열의 원소가 100일때

100 -> 50 -> 25 -> 24 -> 12 -> 6 -> 3 -> 2 -> 1 -> 0이러한 과정으로 9번이 걸리는 것을 알 수 있다.

 

 

코드

 

#include<bits/stdc++.h>
using namespace std;

bool check(const vector<int> & v) {
    for(auto c : v) if(c != 0) return false;
    return true;
}

int main() {
    int N, cnt = 0; cin>>N;
    vector<int> v(N);
    for(int i=0; i<N; i++) cin>>v[i];

    while(true) {
        
        for(int i=0; i<N; i++) {
            if(v[i] == 0) continue;
            int tmp = v[i];
            if(tmp % 2 == 1) {
                v[i] -= 1;
                cnt++;
            }
            v[i] /= 2;
        }

        if(check(v)) break;
        cnt++;
    }

    cout<<cnt;


}

 

'Algorithm' 카테고리의 다른 글

[BOJ] 나무 자르기 14247번 C++  (0) 2024.09.23
[BOJ] 편의점 2 14400번 C++  (1) 2024.09.22
[BOJ] 시간 관리하기 6068번 C++  (0) 2024.09.19
[BOJ] 오셀로 재배치 13413번 C++  (0) 2024.09.18
[BOJ] 강의실 1374번 C++  (4) 2024.09.16
'Algorithm' 카테고리의 다른 글
  • [BOJ] 나무 자르기 14247번 C++
  • [BOJ] 편의점 2 14400번 C++
  • [BOJ] 시간 관리하기 6068번 C++
  • [BOJ] 오셀로 재배치 13413번 C++
따봉치치
따봉치치
따봉치치
김치치의개발블로그
따봉치치
전체
오늘
어제
  • 분류 전체보기 (359)
    • 면접질문 (4)
    • CS (50)
    • FE (116)
      • Javascipt (16)
      • Typescipt (6)
      • React (16)
      • CSS (5)
      • Nextjs (1)
      • 리뷰 (70)
    • Algorithm (181)
    • ETC (3)
      • Bootcamp (4)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 모던 리액트 딥다이브
  • javascript
  • 모던 자바스크립트 딥다이브
  • BFS
  • 자바스크립트
  • C++
  • dp
  • react
  • 자료구조
  • CS
  • 누적합
  • Greedy
  • 백준
  • typescript
  • 완전탐색
  • 데이터베이스
  • Fe
  • 스택
  • BOJ
  • 그리디
  • 그래프 탐색
  • 투 포인터
  • 알고리즘
  • TOPCIT
  • 리액트
  • Stack
  • 우선순위 큐
  • 탐욕 알고리즘
  • 문자열
  • 백트래킹

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
따봉치치
[BOJ] 두 배 더하기 12931번 C++
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.