글 읽기 - 어디를 틀렸는지 도저히 못찾겠습니다.. 제발 도와주십쇼

smu04129 3년 전 0

우선 0으로 시작 하면안되기에

1을먼저 산뒤 그다음을 최대한 0 으로 채운뒤

맨앞수부터 더큰수로 바꿀수있는지 체크하는 방식입니다.

테스트 케이스와 질문글에 있는 반례 다적용해봤는데 옳게 나오더군요

그런데 체점만 하면 1퍼센트에서 그냥 바로 나가리네요

제발 도움을 주십쇼 부탁드립니다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	int x;
	vector<int> v;
	for (int i = 0; i < n; i++) {
		cin >> x;
		v.push_back(x);
	}
	int m;
	cin >> m;
	if (n == 1) { cout << 0; return 0; }
	string s = "";
	s.push_back('1');
	m -= v[1];
	x = m / v.front();
	m %= v.front();
	for (int i = 0; i < x; i++) { s.push_back('0'); }
	for (int i = 0; i < s.length(); i++) {
		m += v[s[i] - '0'];
		bool check = false;
		for (int j = n - 1; j >= 1; j--) {
			if (m >= v[j]) { s[i] = j + '0'; m -= v[j]; break; }
			if (j == 1) { check = true; }
		}
		if (check) { break; }
	}
	cout << s;
}

pichulia 3년 전 1

반례입니다.

3
50 50 1
50

smu04129 3년 전 0

둘째 줄에 각 숫자를 사는데 드는 비용이 작은 숫자부터 주어진다.

이조건에 의해서 저렇게 주어지는 경우는 없지 않나요??

pichulia 3년 전 1

{각 숫자를 사는데 드는 비용}이 {작은 숫자부터} 주어진다.

를

{각 숫자를 사는데 드는 비용이 작은 숫자부터} 주어진다.

로 이해하신거 같네요.

역으로 생각해봅시다.

0, 1, 2 의 비용이 각각 8, 7, 6 일 때는 입력이 어떻게 들어와야 할까요?

{각 숫자를 사는데 드는 비용이 작은 숫자부터} 주어진다고 해석했으면

6 7 8

순으로 입력이 들어온다는 얘긴데

이래서는 6원짜리 숫자가 0 인지 1 인지 2 인지를 알 방법이 없습니다.

문장을 잘못 이해하신거같네요

smu04129 3년 전 0

얘기해주신대로 다시 이해하고

풀이 작성했는데 여전히 바로 1프로에서 틀렸다고 뜨는군요..

페어로 각번호와 가격을 묶어 먼저 가격이 싼순으로 정렬한뒤

가장 싼가격 숫자가 0인경우 먼저 맨앞자리를 그다음순으로 싼번호를 하나 먼저구입을합니다.

그리고 가장싼가격 숫자로 채우고

숫자와 가격묶음 벡터를 이번엔 숫자 크기 순으로 정렬한뒤

문자열 s 를 맨앞부터 검토하며 s[i] 에 있던 것을 팔아 돈을 챙기고 챙긴돈까지 합쳤을때 비용으로 더큰 숫자로 교체할수있는지 검토하는 방식입니다.

무엇이 문제일까요.. 도움을 주시면 감사하겠습니다ㅠ

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

typedef pair<int, int> pi;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	int x;
	vector<pi> v;
	for (int i = 0; i < n; i++) {
		cin >> x;
		v.push_back({ i, x });
	}
	sort(v.begin(), v.end(), [](pi p1, pi p2)->bool {
		if (p1.second == p2.second) { p1.first > p2.first; }
		return p1.second < p2.second;
	});
	int m;
	cin >> m;
	if (n == 1) { cout << 0; return 0; }
	string s = "";
	if (v.begin()->first == 0) {
		s.push_back(v[1].first + '0');
		m -= v[1].second;
	}
	x = m / v.begin()->second;
	m %= v.begin()->second;
	for (int i = 0; i < x; i++) { s.push_back(v.begin()->first + '0'); }
	sort(v.begin(), v.end(), [](pi p1, pi p2)->bool { return p1.first > p2.first; });
	for (int i = 0; i < s.length(); i++) {
		for(const auto j : v)
			if (j.first == s[i] - '0') { m += j.second; break; }
		for (int j = 0; j < n; j++) {
			if (m >= v[j].second && s[i] - '0' < v[j].first) { 
				s[i] = v[j].first + '0'; 
				m -= v[j].second; 
				break; 
			}
		}
	}
	cout << s;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디를 틀렸는지 도저히 못찾겠습니다.. 제발 도와주십쇼

smu04129 3년 전 0

pichulia 3년 전 1

smu04129 3년 전 0

pichulia 3년 전 1

smu04129 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말