[백준 2877번] 4와 7

---

문제 화면

문제 링크 : https://www.acmicpc.net/problem/2877

문제 풀이

이 문제는 수학적인 패턴을 찾아내고 코드로 구현하는게 핵심인 문제이다. 4와 7로만 이루어진 숫자 중에 K번째 작은 수를 출력하는 문제이기 때문에 무조건 패턴이 있을거라는 생각이 들었다.

구상

분명 패턴이 있는데 이 패턴을 어떻게 정리하고 구현할지 고민하다가 K+1의 이진수에서 가장 큰 자리수를 없애면 매칭이 된다는 것을 알게 되었다. 즉, K가 5일때 4와 7로 만들 수 있는 5번째 작은 수는 74인데 위의 그림에서 74를 7을 1로 표현하고 4를 0으로 표현한 이진수로 보았을 때 10으로 되어있다. 이때 5+1(=6)의 이진수는 110이고 여기서 가장 큰 자리수인 1을 없애면 10이 남는다. 이 10이란 숫자를 다시 1은 7로, 0은 4로 변환해서 출력해주면 74가 된다.

제출 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void changeToBinary(int num){
  vector<int> v;
  vector<int>::iterator iter;

  int returnBinary = 0;
  while(num!=0) {
    returnBinary = num % 2;
    v.push_back(returnBinary);
    num /= 2;
  } // K+1을 이진수로 변환(벡터에 저장)

  reverse(v.begin(),v.end()); // 이진수의 값이 거꾸로 들어갔기 때문에 순서대로 변경
  v.erase(v.begin());         // 이진수의 가장 큰 자리 수를 삭제

  for(iter=v.begin(); iter!=v.end(); iter++) {
    if(*iter == 1) cout << "7";
    else cout << "4";
  } // 각 이진수의 자리수를 출력 (1은 7로, 0은 4로)
  
  return;
}

int main() {
  int input; 

  cin >> input;
  changeToBinary(input+1); // K+1을 이진수로 바꾸고 정답을 출력해주는 함수 호출
  
  return 0;
}

결론

이 문제는 수학적인 패턴을 찾고 코드로 구현하는 부분이 핵심이었다. 문제를 푸는 여러가지 다른 방법이 있을 것 같은 문제이다. 창의력이 많이 요구되었던 문제라고 생각된다.