인프런 커뮤니티 질문&답변
작성한 질문수
1-L 다른 방식으로 풀었는데 로직이 아예 잘못된 것인지 궁금합니다.
해결된 질문
작성
·
355
0
안녕하세요!
http://boj.kr/ce148c6b809c4be8bd89dec5973f553e
m이 20만이 넘는 경우 예외처리
입력 받을 때 counting 배열 하나와 벡터 하나에 원소들을 넣기
벡터를 순회하면서 v[i]와 m-v[i]가 둘 다 있는 경우(갑옷을 만들 수 있는 경우) 두 원소를 counting 배열에서 없애고 res ++
v[i]가 곧 m인 경우도 제외했고 (m-v[i] > 0조건)
짝을 찾으면 counting 배열에서 짝을 모두 없애서 중복으로 카운팅하는 경우도 고려했습니다.
답 강의를 듣고 선생님처럼 조합으로 풀면 훨씬 낫다는 사실을 알게 되었지만
저 로직이 잘못된 부분이 어디인지 궁금해서 질문드립니다.
답변 2
0
0
안녕하세요. ㅎㅎ 주석 참고해주세요.
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[100004];
vector<int> v;
int temp;
int res;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
//굿
if (m > 200000) cout << 0 << "\n";
else {
//이게... 카운....팅?
for (int i=0; i<n; i++) {
cin >> temp;
//이거 ++가 되어야 하는거 아닌가요? 똑같은 값 나올 수도 있는데? 2 2 2 나오고 4짜리 만들라고 하면. 정답은 3아닌가요?
arr[temp] = 1;
v.push_back(temp);
}
for (int i=0; i<v.size(); i++) {
if (arr[v[i]] == 1 && m-v[i] > 0 && arr[m-v[i]] == 1) {
arr[v[i]] = 0;
arr[m-v[i]] = 0;
res += 1;
}
}
cout << res << "\n";
}
return 0;
}
답변 감사합니다!
갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다 => 재료는 중복된 값이 주어지지 않는다
이렇게 해석해서 ++로 처리를 하지 않았는데요. 중복값이 주어져도 고유한 번호가 될 수 있나요??
https://www.acmicpc.net/source/share/11b6b5288f774b22b78c3d88d3e5e6f9
위 풀이는 맵을 이용한 풀이인데요
맵으로 풀 때, 문제예시에 나온 값들을 map에 저장할 때 if문을 보시면
map<배열요소, 위치> 로 저장합니다.
이때 {배열요소, 위치} 로 표기하면 {7, 1} 엔트리와 {5, 4} 엔트리는 map에 저장하지 않는데요.
풀이가 통과된 것으로 보아,
배열의 두번째 요소 7을 놓고 보면 배열의 7 이후부터는 2가 나오지 않을 것임을 보장하는 것 같습니다.
yeon _leaf 님의 풀이가 잘 동작할 것이라 생각하는데 그렇지 못한 이유를 못찾겠네요;;
arr배열이 값의 출현 횟수를 체크하지 않고 배열에 포함된 요소인지만 체크하는 용도로 쓰인다는 컨셉을 이해했습니다.
아뇨아뇨 yeon님의 풀이는 틀렸습니다. 중복되는 부분도 고려해주어야 합니다. 고유하다라는 말이 헷갈릴 수가 있긴하네요. 고유하다의 국어사전의 뜻은 "본래부터 가지고 있어 특유하다." 라는 의미입니다. 이말이 중복되지 않는다와는 거리가 있긴해요. ㅎㅎ
감사합니다.
문제가 좀 이상한 것 같아 선생님께 제보드립니다.
선생님 모범답안 (중복된 값이 입력으로 들어올 수 있다)
map을 이용한 제 풀이(중복된 값이 입력으로 들어오지 않을 것이란 전제하에 작성한 풀이)
https://www.acmicpc.net/source/share/439a315b4f854d89bfc893f77266e39d
저는 고유번호가 uniqueNumber의 unique를 생각하여 무기마다 제 각각의 번호가 있을 것이라 생각하여 중복값이 입력으로 없을 것이다 판단했습니다.
둘 다 "맞았습니다!!"가 나왔고
아래 입력에 대해서 같은 결과를 내놓지만
6
9
2 7 4 1 5 3 // (2,7) (4,5) 짝으로 2개.
아래 입력에 대해서는
6
9
2 7 4 2' 5 5'
제 풀이 (2, 7) (4, 5) (4, 5') 짝으로 3개가 나오고
선생님 풀이 (2,7) (7,2') (4,5)(4,5') 짝으로 4개가 나옵니다.
따라서 후자의 테스트케이스의 경우 결과가 다르게 나오는데 두 풀이 모두 성공이 뜨니 이상합니다.
답변 감사합니다! 사전을 보니까 고유하다에 중복이라는 의미가 있다고 생각했던 건 그냥 제 해석이었던 것 같습니다. 앞으로 문장을 더 신경 써서 읽어야겠네요.. 중복값 고려해서 코드 수정해보겠습니다!
ddo님 좋은 말씀 정말 감사합니다.
정정할게요.
이 문제는 "중복된 수가 나오지 않습니다."
yeon님. 제가 yeon님 코드베이스로 몇개의 코드를 수정해서 맞게 만들었습니다. 참고해주세요.
아 이해했습니다. m이 짝수이고 m/2가 배열의 요소로 있을 때 예외처리를 해 줘야 하는군요. 감사합니다!!