BOJ 26258 [다중 일차 함수]

문제

https://www.acmicpc.net/problem/26258

26258번: 다중 일차 함수

 

 

풀이

#include <iostream>
using namespace std;

int cor[100005][2];

int main(){
	ios::sync_with_stdio(false);
    cin.tie(NULL);
    
	int N, Q;
	float x, y, k;
	cin >> N;
	for(int i = 0; i<N; i++){
		cin >> x >> y;
		cor[i][0] = x;
		cor[i][1] = y;
	}
	cin >> Q;
	float result;
	for(int i=0; i<Q; i++){
		cin >> k;
		for(int j = 0; j<N; j++){
			if(cor[j][0] <= k){
				result = cor[j+1][1] - cor[j][1];
			}
		}
		if(result>0){
			cout << 1 << endl;
		}
		else if(result<0){
			cout << -1 << endl;
		}
		else{
			cout << 0 << endl;
		}
	}
	return 0;
}

 

처음에는 위와 같이 c++으로 for문으로 x좌표의 위치를 찾고, 그 위치에서의 기울기를 찾는 방식으로 해결하려고 했다. 하지만 계산 값은 맞지만 시간초과가 떴다. 이 문제를 해결하고자 찾아보던 결과 파이썬에는 bisect 모듈이 있다는 것을 알게 되었다.

 

 

import bisect
import sys
input = sys.stdin.readline
cor_x = [];
cor_y = [];

for i in range(int(input())):
    x, y = map(float, input().split())
    cor_x.append(x)
    cor_y.append(y)
    
for i in range(int(input())):
    k = float(input())
    right = bisect.bisect_right(cor_x, k)
    left = right-1
    grad = cor_y[right] - cor_y[left]
    if grad>0: print(1)
    elif grad<0: print(-1)
    else: print(0)

bisect_right로 k 우측에 있는 가장 작은 x값의 index를 구한 뒤에 1을 빼서 k 좌측에 있는 x값의 index를 구해주었다.