백준 BOJ 16496 - 큰 수 만들기

시험기간인데.....

참고참다가 결국 폭팔했다.

나의 PS를 시험이 막을수는 없지.

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

16496번: 큰 수 만들기

처음 보고 떠오른게

숫자의 자릿수를 일정하게끔 뒤에 0을 붙여서 계산해주는것이었다.

그런데 0을 붙이고 제출을 하자 WA가 나왔었고,

질문검색 란에 반례가 있었다.

 

2

98 988

으로 입력이 들어온다면

내 소스는 98898을 출력했었다.

이걸 해결하기 위해서 고민해본 결과, 9899999999 와 9889999999를 비교하는것을 통해서 해결했다.

여기서의 뒤에 붙는 9는 입력되는 숫자의 첫번째 자리 숫자이다.

 

허나 이 문제를 해결해도 아마 WA가 나올것이다.

이런 입력에서 반례가 생기기 때문이다.

5

0 0 0 0 0

출력이 00000이면 안되고, 0 하나만 출력해줘야 한다.

입력값들을 전부 더해서 0이 아닐 때 출력해주면 된다.

입력값들은 전부 양수이기때문에 모든 수가 0이 아닌 이상 반드시 0 초과의 값을 가진다.

 

소스코드에서 first함수는 첫번째 자리 숫자를 구하는 함수이고,

cmp함수는 비교를 위한 함수이다.

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

using namespace std;
typedef pair<string,int> vec;
vector<vec> v;

int first(long long int k){ while(k>=10) k/=10; return k; }
bool cmp(vec a, vec b){ return a.first+b.first > b.first+a.first; }

int main(){
	int n,k,f;
	long long int tmp=1,chk=0;
	
	cin >> n;
	
	for(int i=0; i<n; i++){
		cin >> k;
		tmp = k;
		f = first(k);
		if(tmp != 0) while(tmp<10000000000LL) tmp = (tmp*10)+f;
		v.push_back({to_string(tmp),k});
	}
	
	sort(v.begin(), v.end(), cmp);
	for(int i=0; i<n; i++) chk += v[i].second;
	if(chk) for(int i=0; i<n; i++) cout << v[i].second;
	else cout << "0";
	return 0;
}

반례처리 (NNNNNN 붙이는거) 에서 좀 애먹었다.

그래도 적당히 AC.

+ 사실 지금 보면 좀 수정할 곳이 보이는 소스이긴 하다

그냥 cmp함수 하나만 썼어도 뚫렸을거같기도 하고,

애초에 cmp함수를 저렇게 수정했던 이유가 기존의 소스코드에서

longlongint형으로 비교하니까 뭔가 문제가 발생해서였다.

나중에 실력이 좀 더 좋아진다면

꼭 longlongint형 비교에서 생기는 원인모를 WA를 해결해보고싶다.