글 읽기 - 투 포인터로 풀었는데 틀린 이유가 궁금합니다!

dudwls901 2년 전 0

제목 그대로 투 포인터로 풀었는데 어디가 틀렸는지 모르겠습니다.

게시판에 있는 예시들은 모두 맞습니다..!

import java.util.*
val br = System.`in`.bufferedReader()
//1<=n<=100
//1<=m<=10000000
fun main() = with(System.out.bufferedWriter()){
    val (n,m) = br.readLine().split(' ').map{it.toInt()}
    val arr = Array(n){Pair(0,0)}
    var idx=0
    var tk = StringTokenizer(br.readLine())
    while(tk.hasMoreTokens()){
        arr[idx++]=Pair(tk.nextToken().toInt(),0)
    }
    tk = StringTokenizer(br.readLine())
    idx=0
    while(tk.hasMoreTokens()){
        arr[idx]=Pair(arr[idx++].first,tk.nextToken().toInt())
    }
    //메모리 오름차순
	arr.sortBy{it.first}
    
	var s = 0
    var e = 0
    var sumByte=0
    var sumCost=0
    while(sumByte<m){
        sumByte+=arr[e].first
        sumCost+=arr[e++].second
    }
    var answer = sumCost
    while(s<n){
        //m보다 작은 경우
		if(sumByte<m){
            if(e==n)break
            sumByte += arr[e].first
            sumCost += arr[e++].second
        }
        //m보다 크거나 같다면 정답 갱신 후 s 증가
        else{
            answer = answer.coerceAtMost(sumCost)
            sumByte -=arr[s].first
            sumCost -=arr[s++].second
        }
    }
    write("$answer")
    close()
}

woongi9 1년 전 1

투포인터일 때는 아래와 같이 결과가 정렬 후의 양 끝에 있는 경우는 찾기 어려울 것 같습니다.

입력

7 120

20 91 92 93 94 95 100

1 2 2 2 2 2 2

정답

dudwls901 1년 전 1

반례 감사합니다.

비용 순 오름차순, 메모리 순 내림차순 정렬해서 위 반례는 해결했으나, 생각해 보니 다른 반례들이 많네요.

dp로 해결했습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

투 포인터로 풀었는데 틀린 이유가 궁금합니다!

dudwls901 2년 전 0

woongi9 1년 전 1

dudwls901 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말