이런 알고리즘 문제는 어떻게 풀어야 할까요 ㅠㅠ 패턴이 파악이 안됩니다! 김성민천사 매우 험난한 산지를 지나는 공중 선로를 건설하려고 한다. 가능한 한 많은 지점에서 선로가 지면과 접하게 하되 오직 한 지점의 최고점(peak)만 허용한다. 선로가 시작하는 지점이나 끝나는 지점이 최고점이 될 수도 있다. 예를 들어 선로가 지날 수 있는 지점의 고도가 다음과 같다고 하자. 5 2 20 19 30 22 45 25 29 10 23 1 3 가능한 한 많은 지점을 지나는 선로의 지점의 수는 7이고 고도는 각각 5, 20, 30, 45, 29, 23, 3 이다. 고도가 각각 2, 19, 22, 25, 29, 10, 1 인 선로도 답이 된다. 입력: 첫 줄에는 지점의 개수가 있고, 그 다음 줄에는 지점들의 고도가 있다. 고도는 모두 서로 다른 정수이다. 고도의 범위는 -1,000,000 이상 +1,000,000 이하이다. 문제가 여러 개일 경우 문제마다 두 줄의 입력이 있다. 입력 예제: 8 : 1 11 3 10 6 4 5 2 6 : 12 11 40 5 3 1 6 : 80 60 30 40 20 10 3 : 5 3 6 출력: 가능한 한 많은 지점을 지나는 선로에 대하여 지점의 수와 고도를 한 줄에 출력한다. 단 선로는 기껏해야 1개의 최고점(peak)를 가져야 한다. 문제가 여러 개일 경우 문제마다 한 줄의 출력이 나온다. 출력 예제: 6 : 1 3 10 6 5 2 5 : 12 11 5 3 1 5 : 80 60 30 20 10 2 : 5 6 우선 처음에 패턴을 파악하려고 맨 처음 예제를 풀어보았는데 두 수를 비교해서 최고 점이 고도가 되더라구요 근데 두번째에서 그게 적용이 안되서 도저히 어떻게 하는지 모르겠습니다 ㅠㅠ 죄송하지만 조금만 도와주세요!! 7년 전
2개의 댓글이 있습니다. skynet dpdp 7년 전 link Corea LIS 문제를 먼저 풀어보시기를 추천합니다. 글에 쓰신 문제는 LIS를 양쪽으로 구해야하는, 한 단계 더 꼬아놓은 문제입니다. 아마 LIS를 해결하시면 이 문제도 해결하실 수 있습니다. 만약 N이 꽤 큰(20,000 이상) 문제라면 MEASURETIME 문제도 풀어보시구요. 7년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
김성민천사
매우 험난한 산지를 지나는 공중 선로를 건설하려고 한다. 가능한 한 많은 지점에서 선로가 지면과 접하게 하되 오직 한 지점의 최고점(peak)만 허용한다. 선로가 시작하는 지점이나 끝나는 지점이 최고점이 될 수도 있다.
예를 들어 선로가 지날 수 있는 지점의 고도가 다음과 같다고 하자.
5 2 20 19 30 22 45 25 29 10 23 1 3
가능한 한 많은 지점을 지나는 선로의 지점의 수는 7이고 고도는 각각 5, 20, 30, 45, 29, 23, 3 이다. 고도가 각각 2, 19, 22, 25, 29, 10, 1 인 선로도 답이 된다.
입력: 첫 줄에는 지점의 개수가 있고, 그 다음 줄에는 지점들의 고도가 있다. 고도는 모두 서로 다른 정수이다. 고도의 범위는 -1,000,000 이상 +1,000,000 이하이다. 문제가 여러 개일 경우 문제마다 두 줄의 입력이 있다.
입력 예제:
8 : 1 11 3 10 6 4 5 2
6 : 12 11 40 5 3 1
6 : 80 60 30 40 20 10
3 : 5 3 6
출력: 가능한 한 많은 지점을 지나는 선로에 대하여 지점의 수와 고도를 한 줄에 출력한다. 단 선로는 기껏해야 1개의 최고점(peak)를 가져야 한다. 문제가 여러 개일 경우 문제마다 한 줄의 출력이 나온다.
출력 예제:
6 : 1 3 10 6 5 2
5 : 12 11 5 3 1
5 : 80 60 30 20 10
2 : 5 6
우선 처음에 패턴을 파악하려고 맨 처음 예제를 풀어보았는데 두 수를 비교해서 최고 점이 고도가 되더라구요 근데 두번째에서 그게 적용이 안되서 도저히 어떻게 하는지 모르겠습니다 ㅠㅠ
죄송하지만 조금만 도와주세요!!
7년 전