글 읽기 - C# 반례 알려주세요.

yhw7979 4년 전 0

DP를 사용하지 않고, 각 카드팩당 1개의 카드에서 얻을 수 있는 비용을 구해서 높은 순서대로 정렬해서

넣을 수 있는 카드팩의 갯수만큼 넣게 해서 비용을 계산했는데

예제도 맞고, 게시판에서 보이는 것도 시도해봤는데 답은 맞는데 실제로 돌려보면 8%정도에서 오답이 나오네요.

혹시 어디가 틀린지 반례를 알려주실 수 있나요?

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        int n;
        int[] arr;

        static void Main(string[] args)
        {
            Program prg = new Program();

            prg.Start();
        }

        public void Start()
        {
            n = int.Parse(Console.ReadLine());

            arr = new int[n];
            List<KeyValuePair<double, int>> valuePerCard =new List<KeyValuePair<double, int>>(); //카드 1개의 가치

            string[] tempVal = Console.ReadLine().Split(' ');
            for (int i=0; i<n; i++)
            {
                arr[i] = int.Parse(tempVal[i]);
                valuePerCard.Add(new KeyValuePair<double, int>(arr[i] / (double)(i + 1), i)); //i+1은 카드 매수, 2번째 인자는 해당 카드팩을 가치 순서대로 정렬할 때 arr에 접근하기 위한 원래 인덱스 저장
            }

            valuePerCard.Sort(delegate(KeyValuePair<double, int> a, KeyValuePair<double, int> b) {
                return a.Key.CompareTo(b.Key);
            });
            valuePerCard.Reverse();

            int totalCards = 0;
            int result = 0;
            for(int i=0; i<valuePerCard.Count; i++) {
                KeyValuePair<double, int> cardpack = valuePerCard[i];
                if (totalCards + cardpack.Value > n)
                { //카드 수가 1팩을 넣어도 초과하면 패스
                    continue;
                }
                int packNum = (n - totalCards) / (cardpack.Value+1);
                result += arr[cardpack.Value]*packNum;
                totalCards += (cardpack.Value + 1) * packNum;
            }

            Console.WriteLine(result);
        }
    }
}

wjsqjawns 4년 전 2

반례입니다.

입력:
5
1 6 8 12 10

정답:
14

출력:
13

yhw7979 4년 전 1

@wjsqjawns 감사합니다. 제가 쓰는 방법으로는 무조건 뒤에 거는 생각을 안하고 고가치 순서대로 다 가져가니까 2+3으로는 계산을 못하는 거였네요. 덕분에 틀렸다는 걸 알았습니다. 감사합니다.

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

문제

문제

출처

ICPC

C# 반례 알려주세요.

yhw7979 4년 전 0

wjsqjawns 4년 전 2

yhw7979 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말