1-L 다른 방식으로 풀었는데 로직이 아예 잘못된 것인지 궁금합니다.
안녕하세요!
http://boj.kr/ce148c6b809c4be8bd89dec5973f553e
m이 20만이 넘는 경우 예외처리
입력 받을 때 counting 배열 하나와 벡터 하나에 원소들을 넣기
벡터를 순회하면서 v[i]와 m-v[i]가 둘 다 있는 경우(갑옷을 만들 수 있는 경우) 두 원소를 counting 배열에서 없애고 res ++
v[i]가 곧 m인 경우도 제외했고 (m-v[i] > 0조건)
짝을 찾으면 counting 배열에서 짝을 모두 없애서 중복으로 카운팅하는 경우도 고려했습니다.
답 강의를 듣고 선생님처럼 조합으로 풀면 훨씬 낫다는 사실을 알게 되었지만
저 로직이 잘못된 부분이 어디인지 궁금해서 질문드립니다.
답변 2
0
yeon님 댓글 참고해주세요~~ 다시 정정해서 올려드렸어요 ㅎㅎ
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;
}0
답변 감사합니다!
갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다 => 재료는 중복된 값이 주어지지 않는다
이렇게 해석해서 ++로 처리를 하지 않았는데요. 중복값이 주어져도 고유한 번호가 될 수 있나요??
0
https://www.acmicpc.net/source/share/11b6b5288f774b22b78c3d88d3e5e6f9
위 풀이는 맵을 이용한 풀이인데요
맵으로 풀 때, 문제예시에 나온 값들을 map에 저장할 때 if문을 보시면
map<배열요소, 위치> 로 저장합니다.
이때 {배열요소, 위치} 로 표기하면 {7, 1} 엔트리와 {5, 4} 엔트리는 map에 저장하지 않는데요.
풀이가 통과된 것으로 보아,
배열의 두번째 요소 7을 놓고 보면 배열의 7 이후부터는 2가 나오지 않을 것임을 보장하는 것 같습니다.
yeon _leaf 님의 풀이가 잘 동작할 것이라 생각하는데 그렇지 못한 이유를 못찾겠네요;;
arr배열이 값의 출현 횟수를 체크하지 않고 배열에 포함된 요소인지만 체크하는 용도로 쓰인다는 컨셉을 이해했습니다.
0
아뇨아뇨 yeon님의 풀이는 틀렸습니다. 중복되는 부분도 고려해주어야 합니다. 고유하다라는 말이 헷갈릴 수가 있긴하네요. 고유하다의 국어사전의 뜻은 "본래부터 가지고 있어 특유하다." 라는 의미입니다. 이말이 중복되지 않는다와는 거리가 있긴해요. ㅎㅎ
감사합니다.
0
문제가 좀 이상한 것 같아 선생님께 제보드립니다.
선생님 모범답안 (중복된 값이 입력으로 들어올 수 있다)
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개가 나옵니다.
따라서 후자의 테스트케이스의 경우 결과가 다르게 나오는데 두 풀이 모두 성공이 뜨니 이상합니다.
0
답변 감사합니다! 사전을 보니까 고유하다에 중복이라는 의미가 있다고 생각했던 건 그냥 제 해석이었던 것 같습니다. 앞으로 문장을 더 신경 써서 읽어야겠네요.. 중복값 고려해서 코드 수정해보겠습니다!
0
ddo님 좋은 말씀 정말 감사합니다.
정정할게요.
이 문제는 "중복된 수가 나오지 않습니다."
yeon님. 제가 yeon님 코드베이스로 몇개의 코드를 수정해서 맞게 만들었습니다. 참고해주세요.
1-E질문입니다!
0
533
2
3-L 틀린 부분 피드백 부탁드립니다.
0
835
2
1-A문제 순열재귀함수 질문입니다.
0
396
1
1-A 일곱난쟁이문제입니다
0
470
1
문제 풀 때 방향성에 대해
0
809
1
맥에서 vs code로 실행 관련 질문입니다
0
530
1
17071번 메모리 초과
0
389
1
1-C질문입니다!
0
428
2
2-B BFS 시간초과질문
0
638
2
1-O 13번 라인
0
447
1
6-J 놀이공원 문제 질문
0
389
1
구현관련 질문
0
491
1
강의 교안
0
321
1
실력을 더 올리고나서 강의를 보는 것이 맞을까요?
0
550
1
안녕하세요! 재귀함수에 관해서 질문드립니다
0
540
1
1-K
0
481
2
3-G번 질문있습니다.
1
480
3
3-C 실행 시간 질문드립니다.
0
503
1
4-A 문제 풀이 질문있습니다.
0
601
2
비트마스킹 연산자 "1의 보수" 영문 표기법
0
441
1
격자탐색 문제에서 BFS 시간복잡도 질문드립니다.
0
349
1
3-O go 함수 질문 드립니다.
1
453
2
4-A 출력 질문
0
307
1
1주차 1-O 질문드립니다
0
265
1