[BOJ/2467] 용액

2021. 5. 2. 19:49·DEV/PS

www.acmicpc.net/problem/2467

2467번: 용액

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -

www.acmicpc.net

github.com/jokj624/PS/blob/master/1000-5000/2467.cpp

jokj624/PS

BOJ, CodeForces 알고리즘 문제 소스코드. Contribute to jokj624/PS development by creating an account on GitHub.

github.com

 한줄 후기 : 그냥 문제가 뭔가 KOI 같았음

 

용액 문제가 뭔가 KOI 스러워서 봤는데 진짜였음 ;; ㅎㄷㄷ

첨 보고 투포인터나 이분탐색 같애~ 이러고 끄고 다른날 (오늘) 풀었는데

투포인터로 풀었다

첨 생각한 방법은

//WA
//BOJ 2467 용액
#include <iostream>
#include <vector>
#include <algorithm>
#define INF 9876543210
using namespace std;
typedef long long ll;
int arr[101010];
int main(){
	int N;
	cin >> N;
	for(int i=0; i<N; i++){
		scanf("%d", &arr[i]);
	}
	int l = 0, r = N-1, ansL=0, ansR=1;
	ll ans = INF;
	while(r >= 0 && l < N ){
		if(l == r)	l++;
		ll sum;
		sum = arr[l]+arr[r];
		if(sum == 0){
			ansL = l;	ansR = r;
			break;
		}
		if(ans > abs(sum)){
			ans = abs(sum);
			ansL = l;
			ansR = r;
		}
		else if(sum < 0){
			l++;	r--;
		}
		else{
			r--; 	l++;
		}
	}
	if(ansL < ansR)		cout << arr[ansL] << " " << arr[ansR];
	else	cout << arr[ansR] << " " << arr[ansL];
	return 0;
}

l = 시작 r=끝 으로 두고 sum (두개 용액을 더한 값)이 0보다 작거나 클때를 찾아서 l을 늘리고 r을 빼줬는데 

생각해보니 저렇게 하면 if문 비교를 할 필요가 없는 코드였다. 아직 한참 멀었음 ㅋㅋ

그래서 엄청나게 틀리고 

//AC
//BOJ 2467 용액
#include <iostream>
#include <vector>
#include <algorithm>
#define INF 9876543210
using namespace std;
typedef long long ll;
int arr[101010];
int main(){
	int N;
	cin >> N;
	for(int i=0; i<N; i++){
		scanf("%d", &arr[i]);
	}
	int l = 0, r = N-1, ansL=0, ansR=1;
	ll ans = INF;
	while(l < r){
		if(l == r)	l++;
		ll sum;
		sum = arr[l]+arr[r];
		if(sum == 0){
			ansL = l;	ansR = r;
			break;
		}
		if(ans > abs(sum)){
			ans = abs(sum);
			ansL = l;
			ansR = r;
		}
		else if(sum < 0){
			l++;
		}
		else{
			r--; 
		}
	}
	if(ansL < ansR)		cout << arr[ansL] << " " << arr[ansR];
	else	cout << arr[ansR] << " " << arr[ansL];
	return 0;
}

고쳐서 맞았다.

sum < 0 이면 현재 값이 음수인거니 (정렬된 수열이므로) l을 늘려준다. 만약 sum > 0이면 양수이니 r을 하나 빼주면 된다.

이런 식으로 비교했을 때, 합이 0 이 나오면 바로 break하면 되고, 그게 아니라면 ans(현재까지 중에 가장 0과 비슷한 합의 값) 과 비교해줘서 더 작은 값으로 갱신해준다.

마지막 출력은 오름차순으로 해야하니 저렇게 비교해 출력한건데, 사실 l<r이라는 while문 조건 때문에 크게 필요 없을 것 같다. 이분 탐색으로도 풀 수 있다고 한다.

저작자표시 비영리 변경금지 (새창열림)

'DEV > PS' 카테고리의 다른 글

제 1회 SMUPC 숙명 프로그래밍 경진대회 참가 후기  (4) 2021.05.09
[BOJ/7569] 토마토, c++  (0) 2021.05.06
[BOJ/1339] 단어 수학, c++  (0) 2021.04.30
[BOJ/2116] 주사위 쌓기, c++  (0) 2021.04.23
[BOJ/2623] 음악 프로그램, c++  (0) 2021.04.08
'DEV/PS' 카테고리의 다른 글
  • 제 1회 SMUPC 숙명 프로그래밍 경진대회 참가 후기
  • [BOJ/7569] 토마토, c++
  • [BOJ/1339] 단어 수학, c++
  • [BOJ/2116] 주사위 쌓기, c++
jobchae
jobchae
말하는 감자지만, 코드를 끄적이는 Node.js 백엔드 개발자입니다.
  • jobchae
    JOBCHAE
    jobchae
  • 전체
    오늘
    어제
    • 🚀 JOBCHAE (177)
      • DEV (146)
        • PS (108)
        • Node.js (12)
        • React (3)
        • docker (1)
        • 잡다한 개발 일지 (20)
        • injection (1)
        • CI CD (0)
        • JS, TS (1)
      • 축구 (0)
      • 일상 (19)
      • 영화 (3)
      • 음악 (8)
  • 블로그 메뉴

    • 💻 Github
    • 🙋🏻 Linkedin
    • 📖 방명록
  • 링크

    • PS Github
  • 공지사항

  • 인기 글

  • 태그

    boj
    typescript
    일상
    mongoDB
    DP
    PS
    GitHub
    nodejs
    리액트
    slack
    렛츠락페스티벌
    SOPT
    앱잼
    node.js
    DFS
    이분탐색
    react
    솝트
    회고
    알고리즘
    위상정렬
    aws
    백준
    슬랙봇
    Nest
    슬랙
    우선순위큐
    Express
    BFS
    Nest.js
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
jobchae
[BOJ/2467] 용액
상단으로

티스토리툴바