[백준] 3649번 로봇 프로젝트

반응형
반응형

문제

상근이와 선영이는 학교 숙제로 로봇을 만들고 있다. 로봇을 만들던 중에 구멍을 막을 두 레고 조각이 필요하다는 것을 깨달았다.

구멍의 너비는 x 센티미터이고, 구멍에 넣을 두 조각의 길이의 합은 구멍의 너비와 정확하게 일치해야 한다. 정확하게 일치하지 않으면, 프로젝트 시연을 할 때 로봇은 부수어질 것이고 상근이와 선영이는 F를 받게 된다. 구멍은 항상 두 조각으로 막아야 한다.

지난밤, 상근이와 선영이는 물리 실험실에 들어가서 레고 조각의 크기를 모두 정확하게 재고 돌아왔다. 구멍을 완벽하게 막을 수 있는 두 조각을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 구멍의 너비 x (1 ≤ x ≤ 20, x는 정수)가 주어진다. x의 단위는 센티미터이다.

다음 줄에는 물리 실험실에 있는 레고 조각의 수 n이 주어진다. (0 ≤ n ≤ 1000000)

다음 n개의 줄에는 레고 조각의 길이 ℓ이 주어진다. ℓ은 양의 정수이며, 단위는 나노미터이다. 블록의 길이는 10 센티미터 (100000000 나노미터)를 넘지 않는다.

출력

각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2)

정답이 여러 개인 경우에는 |ℓ1 - ℓ2|가 가장 큰 것을 출력한다.

 

아 이문제...

생각보다 쉽지 않았다.

내 기준에

 

내 가 한 실수를 열거해보자면

1. 테스트 케이스 여러개라는 말이 무슨 뜻인지 몰랐다.

2. 어떤것을 이분 탐색 대상으로 둘지 생각하지 않았다.

 

첫번째같은 경우, 실수라고는 보기는 어렵지만

테스트 케이스가 여러개인 다른 문제와 달리 이 문제는 어떤 값을 입력해야 종료된다는 조건이 없다.

그래서 더 어려운듯 싶다.

 

처음 이 문제를 시도 했을때, 이분 탐색을 가운데로 두었다.

물론 이렇게해도 답은 맞을 수도 있겠지만(실제로 예제는 답이었다.)

하지만... 이상하게도 틀렸습니다가 나왔다.ㅜㅜ

알고보니, 양 사이드로 값을 찾는 것이 아니라

한쪽 값만 찾으면 되는 문제였다.

그러니까 다른 한쪽은 반복문으로 돌면서 찾은 값이랑 비교했을때,  답이면 정답이었다.

이게 말이 어려운게...

사실 내가 정확히 이해하지 못했기 때문이다.

 

아무튼

원래는 (1+5)/2번을 찾는게 답이지만...

여기에서는

이런 느낌이었다. 

1번 /// (2+5)/2번

아 이게 투포인터구나... 

 

어쩐지...

나중에 이분탐색으로 다시 풀어봐야 겠다.ㅎㅎ(될까?ㅎㅎ)

 

참고로 int* arr 은  int[]arr와 같다.(c++문법 특성상 지원하지는 않지만.ㅜㅜ)

#include <bits/stdc++.h>
using namespace std;
  

bool binary(int x, int n, int* arr) {

    for(int i = 0; i<n;i++) {
      int left = i+1;
      int right = n-1;

      while(left <= right) {

        int mid = (left + right)/2;

        if (arr[i] + arr[mid] == x) {
          cout << "yes " << arr[i] << " " << arr[mid] << "\n";
          return false;
        } else if(arr[i] + arr[mid] > x) {
          right = mid -1;
        } else {
          left = mid +1;
        }

      }
    }

    return true;
}

int main(void) {     
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL);

  int x;
  while(cin >> x) {
    int n;
    cin >> n;
    int arr[n];
    x *= 10000000;
    for(int i = 0;i <n;i++) {
      cin >> arr[i];
    }

    sort(arr,arr+n);

     if(binary(x,n,arr)) {
       cout << "danger\n";
    } 
    
  }
}

 

주의할점은 x는 cm이고 나머지는 나노미터라는걸 알아야한다.

10cm가 100000000나노미터라고 했으니

1cm는 뭘까?

 

이 값으로 구해야한다.

계속적으로 입력해주니 x,n,arr을 매개변수로 넣어주었다.

물론, 초기화 시켜주는것도 하나의 방법이지만 이게 더 나은것같다.

 

도착했는데... x와 같으면?

return false를 해주고

아니라면 true를 리턴 시켜줬다.

 

왜 true를 리턴 시켜줬냐면 !있는것 보다 없는게 나아보였기 때문이다.

 

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int x, n, tmp;
	vector<int> v;
	while (scanf("%d %d", &x, &n) == 2) {
		x *= 10000000;
		bool flag = false;
		v.clear();
		for (int i = 0; i < n; i++) {
			cin >> tmp;
			v.push_back(tmp);
		}
		sort(v.begin(), v.end());
		int s = 0, e = n - 1;
		while (s < e) {
			int sum = v[e] + v[s];
			if (sum == x) {
				cout << "yes " << v[s] << " " << v[e] << endl;
				flag = true;
				break;
			}
			else if (sum < x)
				s++;
			else
				e--;
		}
		if (flag == false)
			cout << "danger" << endl;
	}
	return 0;
}

 

내 코드는 한쪽만 움직였다면

이 코드는 양쪽다 움직이고 있다!

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 2986번 파스칼  (0) 2020.07.06
[백준] 1543번 문서 검색  (0) 2020.07.01
[백준] 1780번 종이의 개수  (0) 2020.06.30
[백준] 1992번 쿼드트리  (0) 2020.06.28
[백준] 14888번 연산자 끼워넣기  (0) 2020.06.27

댓글

Designed by JB FACTORY