문제
양의 정수 $N$이 주어진다. 0부터 9까지의 숫자와 곱하기 *, 거듭제곱 ^의 연산기호를 이용하여 $N$을 표현하는 가장 짧은 길이의 식을 구하시오.
식은 후위 표기법으로 나타내고, 각 수 또는 연산기호는 공백으로 구분한다. 단, 공백은 식의 길이에 포함하지 않는다.
출력
$N$을 표현하는 가장 짧은 길이의 식을 후위 표기법으로 출력한다. 만약 가능한 식이 여러 개 있을 경우 그중 아무거나 하나를 출력한다.
노트
후위 표기법은 연산자를 연산 대상의 뒤에 쓰는 연산 표기법이다. 수식의 앞에서부터 수는 스택에 저장하고, 연산자는 스택에서 두 수를 꺼내 연산하여 스택에 넣는다.
예를 들어, 후위 표기식 3 2 3 * ^는 다음과 같이 729ドル$로 계산된다.
- 3ドル,ドル 2ドル,ドル 3ドル$이 차례로 스택에 들어간다.
- 스택에서 2ドル,ドル 3ドル$을 꺼내 곱한 값 2ドル\times 3 = 6$을 스택에 넣는다.
- 스택에서 3ドル,ドル 6ドル$을 꺼내 거듭제곱한 값 3ドル^6=729$를 스택에 넣는다.
W3sicHJvYmxlbV9pZCI6IjI5NzYyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMjJiXHVjNzkwIFx1YzIwZlx1Y2Y1NFx1YjUyOSIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCAkTiRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAwXHViZDgwXHVkMTMwIDlcdWFlNGNcdWM5YzBcdWM3NTggXHVjMjJiXHVjNzkwXHVjNjQwIFx1YWNmMVx1ZDU1OFx1YWUzMCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KjxcL2NvZGU+PFwvc3Bhbj4sIFx1YWM3MFx1YjRlZFx1YzgxY1x1YWNmMSA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+XjxcL2NvZGU+PFwvc3Bhbj5cdWM3NTggXHVjNWYwXHVjMGIwXHVhZTMwXHVkNjM4XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYyAkTiRcdWM3NDQgXHVkNDVjXHVkNjA0XHVkNTU4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVhZTM4XHVjNzc0XHVjNzU4IFx1YzJkZFx1Yzc0NCBcdWFkNmNcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YzJkZFx1Yzc0MCBcdWQ2YzRcdWM3MDQgXHVkNDVjXHVhZTMwXHViYzk1XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YWNlMCwgXHVhYzAxIFx1YzIxOCBcdWI2MTBcdWIyOTQgXHVjNWYwXHVjMGIwXHVhZTMwXHVkNjM4XHViMjk0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NWNcdWIyZTQuIFx1YjJlOCwgXHVhY2Y1XHViYzMxXHVjNzQwIFx1YzJkZFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM1ZDAgXHVkM2VjXHVkNTY4XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggJE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxIFxcbGVxIE4gXFxsZXEgMTBeOCkkPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+JE4kXHVjNzQ0IFx1ZDQ1Y1x1ZDYwNFx1ZDU1OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWMyZGRcdWM3NDQgXHVkNmM0XHVjNzA0IFx1ZDQ1Y1x1YWUzMFx1YmM5NVx1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjMmRkXHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMWMgXHVjNzg4XHVjNzQ0IFx1YWNiZFx1YzZiMCBcdWFkZjhcdWM5MTEgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1ZDZjNFx1YzcwNCBcdWQ0NWNcdWFlMzBcdWJjOTVcdWM3NDAgXHVjNWYwXHVjMGIwXHVjNzkwXHViOTdjIFx1YzVmMFx1YzBiMCBcdWIzMDBcdWMwYzFcdWM3NTggXHViNGE0XHVjNWQwIFx1YzRmMFx1YjI5NCBcdWM1ZjBcdWMwYjAgXHVkNDVjXHVhZTMwXHViYzk1XHVjNzc0XHViMmU0LiBcdWMyMThcdWMyZGRcdWM3NTggXHVjNTVlXHVjNWQwXHVjMTFjXHViZDgwXHVkMTMwIFx1YzIxOFx1YjI5NCBcdWMyYTRcdWQwZGRcdWM1ZDAgXHVjODAwXHVjN2E1XHVkNTU4XHVhY2UwLCBcdWM1ZjBcdWMwYjBcdWM3OTBcdWIyOTQgXHVjMmE0XHVkMGRkXHVjNWQwXHVjMTFjIFx1YjQ1MCBcdWMyMThcdWI5N2MgXHVhZWJjXHViMGI0IFx1YzVmMFx1YzBiMFx1ZDU1OFx1YzVlYyBcdWMyYTRcdWQwZGRcdWM1ZDAgXHViMTIzXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWQ2YzRcdWM3MDQgXHVkNDVjXHVhZTMwXHVjMmRkIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4zIDIgMyAqIF48XC9jb2RlPjxcL3NwYW4+XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgJDcyOSRcdWI4NWMgXHVhY2M0XHVjMGIwXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPiQzJCwgJDIkLCAkMyRcdWM3NzQgXHVjYzI4XHViODQwXHViODVjIFx1YzJhNFx1ZDBkZFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzJhNFx1ZDBkZFx1YzVkMFx1YzExYyAkMiQsICQzJFx1Yzc0NCBcdWFlYmNcdWIwYjQgXHVhY2YxXHVkNTVjIFx1YWMxMiAkMlxcdGltZXMgMyA9IDYkXHVjNzQ0IFx1YzJhNFx1ZDBkZFx1YzVkMCBcdWIxMjNcdWIyOTRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzJhNFx1ZDBkZFx1YzVkMFx1YzExYyAkMyQsICQ2JFx1Yzc0NCBcdWFlYmNcdWIwYjQgXHVhYzcwXHViNGVkXHVjODFjXHVhY2YxXHVkNTVjIFx1YWMxMiAkM142PTcyOSRcdWI5N2MgXHVjMmE0XHVkMGRkXHVjNWQwIFx1YjEyM1x1YjI5NFx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPlx1YzJkZFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgJDIrMSsxID0gNCRcdWM3NzRcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjk3NjIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJOdW1iZXIgR29sZiIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gYSBwb3NpdGl2ZSBpbnRlZ2VyICROJCwgZmluZCB0aGUgc2hvcnRlc3QgZXhwcmVzc2lvbiB0byByZXByZXNlbnQgJE4kIHVzaW5nIG51bWJlcnMgY29uc2lzdGluZyBvZiBkaWdpdHMgZnJvbSAwIHRvIDksIHRoZSBtdWx0aXBsaWNhdGlvbiBvcGVyYXRvciZuYnNwOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4qPFwvY29kZT48XC9zcGFuPiwgYW5kIHRoZSBwb3dlciBvcGVyYXRvciZuYnNwOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5ePFwvY29kZT48XC9zcGFuPi48XC9wPlxyXG5cclxuPHA+VGhlIGV4cHJlc3Npb24gc2hvdWxkIGJlIHJlcHJlc2VudGVkIGluIHBvc3RmaXggbm90YXRpb24sIGFuZCBlYWNoIG51bWJlciBvciBvcGVyYXRvciBzaG91bGQgYmUgc2VwYXJhdGVkIGJ5IHNwYWNlcy4gSG93ZXZlciwgc3BhY2VzIGFyZSBub3QgY291bnRlZCBpbiB0aGUgbGVuZ3RoIG9mIHRoZSBleHByZXNzaW9uLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIHBvc2l0aXZlJm5ic3A7aW50ZWdlciZuYnNwOyROJC4mbmJzcDskKDEgXFxsZXEgTiBcXGxlcSAxMF44KSQ8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIHNob3J0ZXN0IGV4cHJlc3Npb24gaW4gcG9zdGZpeCBub3RhdGlvbiB0byByZXByZXNlbnQgJE4kLiBJZiB0aGVyZSBhcmUgbXVsdGlwbGUgcG9zc2libGUgZXhwcmVzc2lvbnMsIG91dHB1dCBhbnkgb2YgdGhlbS48XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhlIHBvc3RmaXggbm90YXRpb24mbmJzcDtpcyBhIHdheSB0byB3cml0ZSBhcml0aG1ldGljIG9wZXJhdGlvbnMgd2hlcmUgZXZlcnkgb3BlcmF0b3IgZm9sbG93cyBhbGwgb2YgaXRzIG9wZXJhbmRzLiBZb3Uga2VlcCBudW1iZXJzIG9uIGEgc3RhY2sgYXMgeW91IHByb2Nlc3MgYW4gZXhwcmVzc2lvbiBmcm9tIGxlZnQgdG8gcmlnaHQuIFdoZW4gZW5jb3VudGVyaW5nIGFuIG9wZXJhdG9yLCB5b3UgcG9wIHZhbHVlcyBmcm9tIHRoZSBzdGFjaywgY29tcHV0ZSB0aGUgb3BlcmF0aW9uLCBhbmQgcHVzaCB0aGUgcmVzdWx0IGJhY2sgb250byB0aGUgc3RhY2suPFwvcD5cclxuXHJcbjxwPkZvciBpbnN0YW5jZSwgdGhlIHBvc3RmaXggZXhwcmVzc2lvbiZuYnNwOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4zIDIgMyAqIF48XC9jb2RlPjxcL3NwYW4+Jm5ic3A7aXMgY29tcHV0ZWQgYXMgJDcyOSQ6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+JDMkLCAkMiQsIGFuZCAkMyQmbmJzcDthcmUgcHVzaGVkIG9udG8gdGhlIHN0YWNrIGluIG9yZGVyLjxcL2xpPlxyXG5cdDxsaT5XaGVuIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4qPFwvY29kZT48XC9zcGFuPiBpcyBlbmNvdW50ZXJlZCwgJDIkJm5ic3A7YW5kICQzJCZuYnNwO2FyZSBwb3BwZWQgZnJvbSB0aGUgc3RhY2ssIG11bHRpcGxpZWQgdG8gZ2l2ZSAkNiQsIGFuZCB0aGVuICQ2JCZuYnNwO2lzIHB1c2hlZCBiYWNrIG9udG8gdGhlIHN0YWNrLjxcL2xpPlxyXG5cdDxsaT5XaGVuIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5ePFwvY29kZT48XC9zcGFuPiBpcyBlbmNvdW50ZXJlZCwgJDMkJm5ic3A7YW5kICQ2JCZuYnNwO2FyZSBwb3BwZWQsIGFuZCAkMyQmbmJzcDtpcyByYWlzZWQgdG8gdGhlIHBvd2VyIG9mICQ2JCZuYnNwO3RvIGdpdmUgJDcyOSQsIHdoaWNoIGlzIHRoZW4gcHVzaGVkIG9udG8gdGhlIHN0YWNrLjxcL2xpPlxyXG48XC9vbD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPlRoZSBsZW5ndGggb2YgdGhpcyBleHByZXNzaW9uIGlzICQyKzErMSA9IDQkLjxcL3A+XHJcbiJ9XQ==