인프런 커뮤니티 질문&답변
작성한 질문수
투포인터 boj3273문제 질문
작성
·
95
0
안녕하세요! 투포인터 두 수의 합 문제에서 질문이 있습니다.
a[l]+a[r] == x일 경우에는 l을 움직이면 다음 값이 x보다 더 커지니까 r을 움직여줘야한다고 강의에서 말씀하셨는데요,
주어진 수열이 1245 일 경우, l을 오른쪽으로 움직이면 a[l]+a[r]이 7이 돼서 x보다 더 커지긴 하지만, 다음번 반복에서 어차피 if(a[l]+a[r]>x) r--; 인 경우에 걸려서 r이 왼쪽으로 움직이고, 결국 그 다음번에 합이 6이 되는 것은 마찬가지 아닌가요?
즉 r을 먼저 움직이고 값이 작아졌다가 다시 l을 움직여서 커지느냐 or l을 먼저 움직이고 값이 커졌다가 다시 r을 움직여서 작아지느냐의 차이라고 생각했는데 혹시 l이 아닌 r을 움직여주어야하는 이유가 무엇인지 궁금합니다!
아래 코드는 l을 움직여 주었을 때의 코드입니다 ㅎㅎ
http://boj.kr/92677f37be23452c8c4b9ca54f86dc58
답변 1
0
안녕하세요 밍링님 ㅎㅎ
정말 똑똑하시네요 ㅎㅎ
이걸 찾아내시다니...
네 맞습니다.
r--도 되고 l++로 해도 됩니다.
l++ : {2, 5} -> {2, 4}
r-- : {1, 4} -> {2, 4}
둘 다 가능합니다.
사실 반례를 찾으려고 노력했습니다.
로직
- 합이 크다 -> l++를 해서 값을 줄인다.
- 합이 작다 -> r--를 해서 값을 높인다.
l++라는게 이 명제에 위배되는 것은 아닌가 하구요.
예를 들어
3
1 3 3
4
이 경우에는 l++로 하게 되면 답이 1이 나옵니다.
그러나 ...
3
1 1 3
4
이 경우에는 r--로 하면 답이 1로 나오게 됩니다.
혼돈의 카오스...
자 근데 여기서 중요한 사항이 있는데 문제 지문을 보시면...
n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다
라는 명제가 있습니다.
이 때문에 "같은 수는 존재 하지 않기 때문에" 이부분을 신경쓰지 않고 1, 2, 3 따위의 예시코드를 기반으로 생각을 해봤을 때 l++나 r-- 둘 다 가능한 것을 알 수 있습니다.
이는 다음과 같이 설명할 수 있습니다.
예를 들어 0과 6이라는 인덱스를 기반으로 ret을 찾았다고 해봅시다.
자 다음에는 {0, 6}을 확인할 필요는 없으며
그 범위안에서의 부분조합을 기반으로 확인해야 합니다.
{1, 6} 또는 {0, 5} 식으로 가야 합니다.
l++하는 경우
0, 6 -> 1, 6
- 만약 값이 작다면 -> 2, 6이 되겠죠?
- 만약 값이 크다면 -> 1, 5를 하겠죠?
여기서 {0, 5} 부분을 체크하지 못합니다. -> 하지만 문제가 되지 않습니다. 어차피 {0, 6}이 답이 된 이상 {0, 5} 가 답이 될 확률은 없습니다.
ex) 1, 2, 3, 4 이고 5를 찾는데 1, 4 조합 이후 -> 1, 3은 답이 절대 아니다!
r--를 하는 경우
0, 6 -> 0, 5
- 만약 값이 작다면 -> 1, 5를 하겠죠?
- 만약 값이 크다면 -> 0, 4를 하겠죠?
여기서 {1, 6} 부분을 체크하지 못합니다. -> 하지만 문제가 되지 않습니다. 어차피 {0, 6}이 답이 된 이상 {1, 6} 가 답이 될 확률은 없습니다.
해당 부분은 강의내에 수정하도록 하겠습니다.
좋은 지적을 해주셔서 감사합니다.
큰돌선생님 감사합니다! 아닙니당 선생님 덕분에 코드 이해하고 그리디 문제도 공부할 수 있게 된걸요! 다 선생님 덕분입니다~~ 좋은 강의와 빠르고 구체적인 답변 늘 감사합니다 ㅎㅎ