[paiza]いとおかし（ 【殿堂入りキャンペーン】お菓子の詰め合わせ (paizaランク A 相当)

年に2～3回ぐらい

ありがたいことにお土産で「萩の月」をいただくことがあるんですが、
もうあの甘さとスポンジの食感がシンドくてシンドくて。。。
年に1回あるかないかぐらいのペースで食べたいところです。
※貰ってばかりで言える立場にないですが、他にお土産無いんか？

チェック処理とかは端折ってる

/** ここから定型文 */
ここで記載したクラスについては、
こっちの記事に書いてある、標準入力をList化したりしてるMainクラスから呼び出す予定だし・なんか継承したりしてるYO!!

ちな、Mainを実行して標準入力から入力するのクソ面倒くさいので、
Java編については問題の入力例をパラメータにしたテストクラスとかも作って公開するYO!!

開発・実行環境はこんな感じ

• VSCode
• Java 17
• jUnit 5.9
• maven

pom.xmlはこんな感じ

pom.xml

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>jp.co.asil</groupId>
    <artifactId>paiza202408</artifactId>
    <version>1.0-SNAPSHOT</version>

    <properties>
        <maven.compiler.source>17</maven.compiler.source>
        <maven.compiler.target>17</maven.compiler.target>
    </properties>

    <dependencies>
        <dependency>
            <groupId>org.junit.jupiter</groupId>
            <artifactId>junit-jupiter-engine</artifactId>
            <version>5.9.1</version>
            <scope>test</scope>
        </dependency>
    </dependencies>
</project>

/** ここまで定型文 */

実装クラス

SchoolHiking.java

package jp.co.asil.paiza202408;

import java.util.Arrays;
import java.util.List;

public class SchoolHiking extends Question {
  private int budget;
  private int[] prices;

  public SchoolHiking(List<String> list) {
    super(list);
    int[] cond = List.of(list.get(0).split(" ")).stream().mapToInt(Integer::parseInt).toArray();
    this.budget = cond[1];
    this.prices = list.subList(1, list.size()).stream().mapToInt(Integer::parseInt).toArray();
  }

  @Override
  public List<String> answer() {

    // dp[j]：j円で購入可能な最大のお菓子の種類数
    int[] dp = new int[budget + 1];
    Arrays.fill(dp, -1);
    dp[0] = 0;

    for (int price : prices)
      for (int j = budget; j >= price; j--)
        if (dp[j - price] != -1)
          dp[j] = Math.max(dp[j], dp[j - price] + 1);

    int maxTypes = 0;
    int minChange = budget;

    for (int i = 0; i <= budget; i++) {
      if (dp[i] > maxTypes) {
        maxTypes = dp[i];
        minChange = budget - i;
      } else if (dp[i] == maxTypes) {
        minChange = Math.min(minChange, budget - i);
      }
    }
    return List.of(String.valueOf(minChange));
  }

}

テストクラス

SchoolHikingTest.java

package jp.co.asil.paiza202408;

import static org.junit.jupiter.api.Assertions.assertEquals;

import java.util.List;

import org.junit.jupiter.api.Test;

public class SchoolHikingTest {
  @Test
  void testAnswer1() {
    SchoolHiking testClass = new SchoolHiking(List.of("3 300",
        "150",
        "120",
        "130"));
    assertEquals(testClass.answer().get(0), "20");
  }

  @Test
  void testAnswer2() {
    SchoolHiking testClass = new SchoolHiking(List.of("4 1000",
        "200",
        "20",
        "500",
        "60"));
    assertEquals(testClass.answer().get(0), "220");
  }

  @Test
  void testAnswer3() {
    SchoolHiking testClass = new SchoolHiking(List.of("5 300",
        "150",
        "120",
        "130",
        "75",
        "55"));
    assertEquals(testClass.answer().get(0), "20");
  }

  @Test
  void testAnswer4() {
    SchoolHiking testClass = new SchoolHiking(List.of("5 300",
        "150",
        "120",
        "130",
        "70",
        "55"));
    assertEquals(testClass.answer().get(0), "25");
  }
}

解説

JavaScript版を見て！

一応テストクラスの方に、JavaScript版でもテストしたケースを追加してみました。