해결된 질문
24.09.15 14:45 작성
·
24
0
안녕하세요 선생님. 먼저 해피추석 보내십쇼!!
http://boj.kr/7fdb0fc2859a40888f5c0cd3583076ab
제가 궁금한 것은 두가지 입니다.
위 방식대로 접근한것이 괜찮은지
31번째 줄에서의 문제
31번째 줄에서 절대값을 이용했더니 답이 틀렸습니다.
제출된 코드는 정답으로 나오는데 두 수의 차이에서 절대값을 넣었을 때 왜 틀리는지 모르겠습니다.
// 틀림
auto it = find(start, numbers.end(), abs(numbers[i] - m));
// 맞음
auto it = find(start, numbers.end(), m - numbers[i]);
답변 2
1
2024. 09. 15. 17:56
안녕하세요 김준님 ㅎㅎ
만약 abs
를 사용한다면, m = 10
이고 numbers[i] = 14
일 때, abs(10 - 14) = abs(-4) = 4
가 됩니다. 즉 -4가 나와서 -> 해당 경우의 수는 배제가 되어야 하는데 갑자기 4를 찾게 되서 UB가 발생하게 됩니다.
하지만 이 abs를 쓸 수 있는 방법이 있습니다.
바로 sort() 오름차순을 쓰면 되는데요.
예를 들어
오름차순 정렬을 하면 -> a, m , b 이렇게 있다고 했을 때 a < m < b는 자명합니다.
여기서 m - a는 b가 나오며 양수입니다. 자 그 다음 b를 만났을 때 어차피 start부터 탐색을 이어나가니 abs를 걸어서 -> 양수 a가 나오더라도 a는 탐색범위에서 벗어나니 abs를 써도 로직상 문제가 없게 됩니다.
전체 코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
/*
갑옷 재료는 번호가 있다.
갑옷은 2개의 재료로 만든다.
두 갑옷의 번호를 합쳐 M이 되면 갑옷이 된다.
1 <= M <= 10,000,000
N개의 재료, 1 <= N <= 15,000
1 <= 고유번호 <= 100,000
numbers[a,b,c,...]
a + b = m
*/
void Solution(int n, int m, vector<int> &numbers)
{
int sum = 0;
if (n == 1 || m == 1 || m > 200'000)
{
cout << sum << '\n';
return;
}
sort(numbers.begin(), numbers.end());
for (int i = 0; i < n; i++)
{
auto start = numbers.begin() + 1 + i;
auto it = find(start, numbers.end(), abs(m - numbers[i]));
if (it != numbers.end())
sum++;
}
cout << sum << '\n';
}
int main()
{
int n;
int m;
cin >> n >> m;
vector<int> numbers;
for (int i = 0; i < n; i++)
{
int num;
cin >> num;
numbers.push_back(num);
}
Solution(n, m, numbers);
return 0;
}
김준님도 즐추보내세요 ㅎㅎ
감사합니다.
0
안녕하세요, 인프런 AI 인턴입니다. 김준님!
추석 인사 감사드리고요, 질문주신 내용을 확인했습니다. 두 가지 질문에 대해 답변드리겠습니다.
위 방식으로 문제를 접근하는 것은 일반적이며, find 함수를 사용하는 것도 적절한 방식입니다.
절대값을 사용하는 것과 단순히 뺄셈을 사용하는 것의 결과 차이로 인해 발생한 문제입니다.
절대값을 사용한 경우와 그렇지 않은 경우의 차이:
// 틀림
auto it = find(start, numbers.end(), abs(numbers[i] - m));
// 맞음
auto it = find(start, numbers.end(), m - numbers[i]);
문제를 구체적으로 이해하기 위해 아래 URL들을 참고해 주세요:
- 2-F abs사용
이 질문에서도 abs 함수 사용 관련 오류에 대한 해결 방안을 설명하고 있습니다.
- 2309 뭐가 틀린건지 모르겠습니다.
알고리즘과 관련된 접근법과 디버깅 방법에 대해 다룹니다.
간단히 답변드리자면, abs(numbers[i] - m)
을 사용하면 문제의 의도와 다르게 작동할 수 있습니다. 문제 본문에서 제시된 예시는 단순 뺄셈을 사용하여 의도한 값과 맞추는 것이 바람직합니다. 절대값은 방향성과 관계없이 크기만 고려하기 때문에 결과적으로 다른 요소들을 찾게 되어 오류가 발생할 수 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.