BOJ 15311 - 약팔기

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

문제 풀이

친구가 재밌는 문제라고 풀어보라고 했던 문제가 백준에, 심지어는 나는코더다 2017 송년대회에 있을줄은 몰랐다.

아이디어성 문제이다. 루트, 버킷에 익숙한 사람은 좀 더 쉽게 보일 수도 있다.

사실 풀이를 어떻게 써야할지 모르겠다. 그래도 최대한 사고의 흐름을 써보려고 한다.

맨 처음에는 이진법을 생각했다. 모든 값을 다 표기하는데 이진법만큼 쉽고 간단한 방법이 떠오르지 않았다. 하지만 이진법은 자릿수가 계속 올라간다는 문제가 있었다. 1 2 1 4 2 1 뭐 이런식으로 할 수도 없었고, 자릿수가 많은 표기법은 좋지 못하다는 생각을 했다. 2000과 1000000을 계속 생각해봤다. $n^k=1000000$이고 $n*k=2000$ 인 n과 k를 찾아야 한다. 직관적으로 1000, 2라는 것을 알 수 있다

앞에 999개를 1로 채우고 뒤에 1000개를 1000으로 채우면 문제가 해결된다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
int main(){
    cout<<2000<<'\n';
    for(ll i=1;i<=1000;i++)
        cout<<'1'<<' ';
    for(ll i=1;i<=1000;i++)
        cout<<"1000"<<' ';
}