[Java/Python3] 백준 25947. 선물할인

문제

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

25947번: 선물할인

조건을 만족하며 최대로 살 수 있는 선물의 수를 출력한다.

 

 

풀이

 

풀이는 다음과 같다.  int left, right 를 선언해주어 left .. right 범위 내의 윈도우 슬라이드에 담긴 물건들을 "할인해서 구매한 물건들" 로 정의하였다. 

1. 주어진 배열 오름차순 정렬
2. 먼저 할인 가능하면 가능한 만큼 일단 구매한다.
3. 더 이상 할인 할 수 없으면 left 에 위치한 물건을 정가로 구매한다.,, left++
4. 애초에 할인 변수 a == 0 이면, 예외처리 해준다.
5. right 만큼 구매한 것임으로 right를 출력한다. 

문제의 요점은 "최대한 많은 물건을 구입하자 " 임으로 우선 할인 가능한 만큼 구매해주고 , 윈도우 슬라이드 범위를 유지하면서 물건을 구매 해주면 OK ! 

 

참고

자바에서는 누적합으로 비교하면 int형이 아닌 long형으로 해주어야 한다. 따라서 누적합을 계산하는 대신 현재 남은 예산 에서 다음 번쨰 구매할 가격 만큼 뺄셈을 해 주었다. 

if(right - left < a){
                    b-=nums[right]/2;//할인된가격 산다.
                    if(b < 0) break;
                    right++;
                }else{
                    if(a >0)b-=nums[left++]/2;
                    else {
                        b-= nums[right];
                        if(b < 0)break;
                        right++;
                    }
                }

처음에 같은 로직인데 정수를 리턴하는 코드가 아닌 System.out.println(ans) 하는 식으로 했는데 출력 초과가 났다... 답답해서 그냥 다시 짰다. 

 

코드

자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    int n, b, a;
    int nums[];
    public static void main(String args[]) throws IOException {
        Main m = new Main();
        m.sol();

    }
    public int getN(){
        boolean temp = true;
        int right =0;
        int left =0;
        for(int i = 0 ;i < a ; i++){
            b-=nums[i]/2;
            right = i+1;
            if(b < 0){
                temp = false;
                return i;
            }
        }
        if(temp){
            while(right < n){

                if(right - left < a){
                    b-=nums[right]/2;//할인된가격 산다.
                    if(b < 0) break;
                    right++;
                }else{
                    if(a >0)b-=nums[left++]/2;
                    else {
                        b-= nums[right];
                        if(b < 0)break;
                        right++;
                    }
                }
            }
            return right;
        }
        return right;
    }
    public void sol() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String q = br.readLine();
        n= Integer.parseInt(q.split(" ")[0]);
        b= Integer.parseInt(q.split(" ")[1]);
        a = Integer.parseInt(q.split(" ")[2]);//최대 선물의 수d
        nums = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i =0; i< n;i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(nums);
        System.out.println(getN());
    }


}

파이썬

class Main():

    def __init__(self):
        n, b, a = map(int, input().split())
        nums = list(map(int, input().split()))
        nums.sort()
        print(self.getN(n,b,a,nums))

    def getN(self,n,b,a,nums):
        right =0 
        left =0 
        for i in range(a):#할인가능한만큼 산다. 
            b-=nums[i]//2
            right = i+1
            if b < 0 : return i
        
        while right < n:
            if right - left < a: #슬라이딩 개수 < 할인 개수
                b-= nums[right]//2
                if b < 0 : break
                right +=1
            else:       # 슬라이딩 개수 >= 할인 개수
                if a > 0 : 
                    b-=nums[left]//2 #nums[left]는 정가로 산다.
                    left+=1
                else: #예외 처리
                    b-=nums[right]
                    if b < 0 : break
                    right +=1 
        return right

a = Main()