https://www.acmicpc.net/problem/2467
๋ฌธ์
KOI ๋ถ์ค ๊ณผํ์ฐ๊ตฌ์์์๋ ๋ง์ ์ข ๋ฅ์ ์ฐ์ฑ ์ฉ์ก๊ณผ ์์นผ๋ฆฌ์ฑ ์ฉ์ก์ ๋ณด์ ํ๊ณ ์๋ค. ๊ฐ ์ฉ์ก์๋ ๊ทธ ์ฉ์ก์ ํน์ฑ์ ๋ํ๋ด๋ ํ๋์ ์ ์๊ฐ ์ฃผ์ด์ ธ์๋ค. ์ฐ์ฑ ์ฉ์ก์ ํน์ฑ๊ฐ์ 1๋ถํฐ 1,000,000,000๊น์ง์ ์์ ์ ์๋ก ๋ํ๋ด๊ณ , ์์นผ๋ฆฌ์ฑ ์ฉ์ก์ ํน์ฑ๊ฐ์ -1๋ถํฐ -1,000,000,000๊น์ง์ ์์ ์ ์๋ก ๋ํ๋ธ๋ค.
๊ฐ์ ์์ ๋ ์ฉ์ก์ ํผํฉํ ์ฉ์ก์ ํน์ฑ๊ฐ์ ํผํฉ์ ์ฌ์ฉ๋ ๊ฐ ์ฉ์ก์ ํน์ฑ๊ฐ์ ํฉ์ผ๋ก ์ ์ํ๋ค. ์ด ์ฐ๊ตฌ์์์๋ ๊ฐ์ ์์ ๋ ์ฉ์ก์ ํผํฉํ์ฌ ํน์ฑ๊ฐ์ด 0์ ๊ฐ์ฅ ๊ฐ๊น์ด ์ฉ์ก์ ๋ง๋ค๋ ค๊ณ ํ๋ค.
์๋ฅผ ๋ค์ด, ์ฃผ์ด์ง ์ฉ์ก๋ค์ ํน์ฑ๊ฐ์ด [-99, -2, -1, 4, 98]์ธ ๊ฒฝ์ฐ์๋ ํน์ฑ๊ฐ์ด -99์ธ ์ฉ์ก๊ณผ ํน์ฑ๊ฐ์ด 98์ธ ์ฉ์ก์ ํผํฉํ๋ฉด ํน์ฑ๊ฐ์ด -1์ธ ์ฉ์ก์ ๋ง๋ค ์ ์๊ณ , ์ด ์ฉ์ก์ ํน์ฑ๊ฐ์ด 0์ ๊ฐ์ฅ ๊ฐ๊น์ด ์ฉ์ก์ด๋ค. ์ฐธ๊ณ ๋ก, ๋ ์ข ๋ฅ์ ์์นผ๋ฆฌ์ฑ ์ฉ์ก๋ง์ผ๋ก๋ ํน์ ๋ ์ข ๋ฅ์ ์ฐ์ฑ ์ฉ์ก๋ง์ผ๋ก ํน์ฑ๊ฐ์ด 0์ ๊ฐ์ฅ ๊ฐ๊น์ด ํผํฉ ์ฉ์ก์ ๋ง๋๋ ๊ฒฝ์ฐ๋ ์กด์ฌํ ์ ์๋ค.
์ฐ์ฑ ์ฉ์ก๊ณผ ์์นผ๋ฆฌ์ฑ ์ฉ์ก์ ํน์ฑ๊ฐ์ด ์ ๋ ฌ๋ ์์๋ก ์ฃผ์ด์ก์ ๋, ์ด ์ค ๋ ๊ฐ์ ์๋ก ๋ค๋ฅธ ์ฉ์ก์ ํผํฉํ์ฌ ํน์ฑ๊ฐ์ด 0์ ๊ฐ์ฅ ๊ฐ๊น์ด ์ฉ์ก์ ๋ง๋ค์ด๋ด๋ ๋ ์ฉ์ก์ ์ฐพ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์๋ ์ ์ฒด ์ฉ์ก์ ์ N์ด ์ ๋ ฅ๋๋ค. N์ 2 ์ด์ 100,000 ์ดํ์ ์ ์์ด๋ค. ๋์งธ ์ค์๋ ์ฉ์ก์ ํน์ฑ๊ฐ์ ๋ํ๋ด๋ N๊ฐ์ ์ ์๊ฐ ๋น์นธ์ ์ฌ์ด์ ๋๊ณ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฅ๋๋ฉฐ, ์ด ์๋ค์ ๋ชจ๋ -1,000,000,000 ์ด์ 1,000,000,000 ์ดํ์ด๋ค. N๊ฐ์ ์ฉ์ก๋ค์ ํน์ฑ๊ฐ์ ๋ชจ๋ ์๋ก ๋ค๋ฅด๊ณ , ์ฐ์ฑ ์ฉ์ก๋ง์ผ๋ก๋ ์์นผ๋ฆฌ์ฑ ์ฉ์ก๋ง์ผ๋ก ์ ๋ ฅ์ด ์ฃผ์ด์ง๋ ๊ฒฝ์ฐ๋ ์์ ์ ์๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ํน์ฑ๊ฐ์ด 0์ ๊ฐ์ฅ ๊ฐ๊น์ด ์ฉ์ก์ ๋ง๋ค์ด๋ด๋ ๋ ์ฉ์ก์ ํน์ฑ๊ฐ์ ์ถ๋ ฅํ๋ค. ์ถ๋ ฅํด์ผ ํ๋ ๋ ์ฉ์ก์ ํน์ฑ๊ฐ์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ถ๋ ฅํ๋ค. ํน์ฑ๊ฐ์ด 0์ ๊ฐ์ฅ ๊ฐ๊น์ด ์ฉ์ก์ ๋ง๋ค์ด๋ด๋ ๊ฒฝ์ฐ๊ฐ ๋ ๊ฐ ์ด์์ผ ๊ฒฝ์ฐ์๋ ๊ทธ ์ค ์๋ฌด๊ฒ์ด๋ ํ๋๋ฅผ ์ถ๋ ฅํ๋ค.
๊ณจ๋5 ๋ฌธ์ .
์ ํ์ ์ธ ํฌํฌ์ธํฐ ๋ฌธ์ ์ด๋ค!
์ฒ์์ nowsum์ ๊ตฌํ ๋ abs๋ฅผ ์ ์ฉํด๋ฒ๋ฆฌ๋ ๋ฐ๋์, ํฌ์ธํฐ๊ฐ ์ ๋๋ก ์ ์์ง์์..
์ธ์ ์ ๋๊ฐ์ ์ฐ๊ณ , ์ธ์ ์ ์ฐ๋์ง ์ ํ์ ํด์ ๋ฃ์ด์ค์ผํ๋ค.
๋์ ํ์ด
#include <iostream>
using namespace std;
int main(){
int n;
int num[100001] = {0};
cin >> n;
for (int i = 0; i < n; ++i){
cin >> num[i];
}
int left = 0;
int right = n - 1;
int minsum = abs(num[left] + num[right]);
int minleft = num[left];
int minright = num[right];
for (int i = 0; i < n; ++i){
int nowsum = num[left] + num[right];
if (minsum > abs(nowsum)){
minsum = abs(nowsum);
minleft = num[left];
minright = num[right];
if(minsum==0) break;
}
if(nowsum > 0) right--;
if(nowsum < 0) left++;
if(right == left) break;
}
cout << minleft << " " << minright;
}
'๐ ์๊ณ ๋ฆฌ์ฆ > BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[C++/BOJ] 17836 : ๊ณต์ฃผ๋์ ๊ตฌํด๋ผ! (์๋ฎฌ๋ ์ด์ ) / ์ฝ์ง ๊ธฐ๋ก (0) | 2023.03.23 |
---|---|
[C++/BOJ] 1806 : ๋ถ๋ถํฉ (ํฌํฌ์ธํฐ) (0) | 2023.03.23 |
[C++/BOJ] 10942 : ํฐ๋ฆฐ๋๋กฌ? (DP) (0) | 2023.03.18 |
[C++/BOJ] 12865 : ํ๋ฒํ ๋ฐฐ๋ญ (DP) / ํ ์คํธ์ผ์ด์ค ํฌํจ (1) | 2023.03.17 |
[C++/BOJ] 1890 : ์ ํ (DP) (1) | 2023.03.16 |