[백준 BOJ] 1094번 막대기 (C++/cpp)

문제 설명

https://www.acmicpc.net/problem/1094

1094번: 막대기

 

접근 방법 - 이진법의 원리에 대한 수학적 연산 문제

백준의 1094번 문제는 이진법 연산을 활용하여 해결해야 하는 수학 문제이다.

해당 문제는, 특정 규칙에 따라 입력받은 길이의 막대기를 만드는 데에 필요한 막대기의 수를 측정해야 하는 문제이다.

문제에 적혀있는 규칙과 막대기의 시작을 64cm로 하였다는 점을 보았을 때에 이진법의 연산을 활용해야 한다는 점을 알 수 있다.

하지만 필자는 문제에 보인대로 코드를 작성하였고 그렇게 해결해버렸다.

그렇기 때문에 이진법의 연산 방법으로 해당 문제를 해결하는 중이었다면, 그대로 뒤로 가기를 조심스럽게 권한다.

하지만 문제에 제시된 대로 코드를 작성하여도 오답 처리는 안 되어서, 이 방법으로 하는 데에 어려움이 있었다면 아래 코드와 설명을 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 만들고자 하는 막대기의 길이(n)를 입력받는다.

 

2) 아래처럼 변수들을 선언한다.

- 첫 막대기는 64cm로 시작한다. 따라서, 연산에 사용할 변수 num을 64로 초기화하여 선언한다.

- 잘라진 막대기들의 합을 구하기 위한 변수 sum을 0으로 초기화하여 선언한다.

- 막대기의 개수를 카운팅할 변수 cnt를 0으로 초기화하여 선언한다.

 

3) 반복문을 실행하여 아래의 연산을 취한다. 해당 반복문은 sum이 n과 동일해질 때까지 실행한다.

- 만일 num과 sum의 합이 n보다 크다면, 이 상태로는 n의 크기만큼의 막대기를 만들 수 없다.

따라서, num을 2로 나눈 뒤 반복문의 처음으로 돌아간다.

- num과 sum의 합이 n보다 작거나 같다면, n의 크기에 근접하거나 동일한 막대기를 만들 수 있다.

따라서, sum에 현재의 num을 더한 뒤 cnt에 1을 더한다. 그리고 num을 2로 나눈 값을 저장한 뒤 반복문의 처음으로 돌아간다.

 

4) 3)의 반복문 실행이 종료되었다면, 최종적으로 저장된 cnt의 값을 출력하고 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 1094번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n;
	cin >> n;

	int num = 64;
	int sum = 0;
	int cnt = 0;
	while (sum != n) {
		if (num + sum > n) {
			num /= 2; 
			continue; 
		}
		sum += num;
		cnt++;
		num /= 2;
	}
	cout << cnt << endl;
}

 

제출 결과

(2022.04.16 백준 1094번 문제 제출 결과)