백준 1027번 c++ and java

문제

세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)은 (i,0)부터 (i,높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 빌딩의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 1번 빌딩부터 그 높이가 주어진다. 높이는 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1 복사

15
1 5 3 2 6 3 2 6 4 2 5 7 3 1 5

예제 출력 1 복사

7

예제 입력 2 복사

1
10

예제 출력 2 복사

0

예제 입력 3 복사

4
5 5 5 5

예제 출력 3 복사

2

예제 입력 4 복사

5
1 2 7 3 2

예제 출력 4 복사

4

예제 입력 5 복사

10
1000000000 999999999 999999998 999999997 999999996 1 2 3 4 5

예제 출력 5 복사

6

 

이 문제는 기울기를 이용한 브루트포스 문제이다.

 

 

문제의 로직

 

1. 입력을 모두 받아준다.

2. 이중 포문을 돌리고 이중 포문이 시작할 때 마다 double max를 선언해준다.

3. max보다 더 큰 기울기가 나올 때 마다 max를 갱신해 준다.

4. 기울기를 연결시키는 두 점을 모두 ++를 해 준다. (오른쪽 방향, 왼쪽 방향 모두 보이는 건물이므로)

5. count에서 제일 큰 값을 출력해 준다.

 

 

기울기 공식

y2-y1 / x2-x1

 

중요한 점

기울기는 int가 아닌 double로 할당해 주자.

 

 

- c++

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


int n;
vector<int>v;


int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        v.push_back(a);
    }


    vector<int>count(51);

    for(int i = 0 ; i < n ; i ++){
        double max = -1000000000;
        for(int j = i+1 ; j < n ; j++){
            if(max < double(v[i]-v[j])/double(i-j)){
                max = double(v[i]-v[j])/double(i-j);
                count[i]++;
                count[j]++;
            }
        }
    }

    cout << *max_element(count.begin(),count.end());









    return 0;

}

 

- java

 

import java.io.*;
import java.util.*;


public class Main {



    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        ArrayList<Integer> arrayList = new ArrayList<Integer>();

        int [] count = new int[51];

        while(st.hasMoreTokens()){
            arrayList.add(Integer.parseInt(st.nextToken()));
        }

        for (int i = 1; i <=n ; i++) {
            double max = -1000000000;
            for (int j = i+1; j <=n ; j++) {

                if(max < Double.valueOf(arrayList.get(i-1)-arrayList.get(j-1) )/Double.valueOf(i-j) ){
                    max = Double.valueOf(arrayList.get(i-1)-arrayList.get(j-1) )/Double.valueOf(i-j);
                    count[i]++;
                    count[j]++;

                    //System.out.println(arrayList.get(i-1) + " " + arrayList.get(j-1) + " " + i + " " + j + " " + max);
                }

            }
        }

//        for(int i = 0 ; i < n ; i++ ){
//            System.out.println(count[i]);
//
//        }


        System.out.println(Arrays.stream(count).max().getAsInt());




    }
}