[TIL]2025.05.17(토)

알고리즘

DP문제를 오랜만에 풀었다. 1,2,3 더하기 문제는 다행히 20분 안걸려서 풀었다. 

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

import java.io.*;
import java.util.*;

public class Main {
  public static ArrayList<Integer> list = new ArrayList<>();
  public static int N, MOD = 1_000_000_009, max;

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    input(br);
    pro();
  }

  static void pro()  {
    int[] dp = new int[max + 1];
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for (int i = 4; i <= max; i++) {
      dp[i] = dp[i - 1] + dp[i - 2];
      dp[i] %= MOD;
      dp[i] += dp[i - 3];
      dp[i] %= MOD;

    }
    StringBuilder sb = new StringBuilder();
    for(int i : list){
      sb.append(dp[i]).append("\n");
    }
    System.out.println(sb);
  }

  static void input(BufferedReader br) throws Exception {
    N = Integer.parseInt(br.readLine());
    for(int i = 0; i < N; i++) {
      int n = Integer.parseInt(br.readLine());
      max = Math.max(max, n);
      list.add(n);
    }
  }
}

여기서 한번 해매었던 부분은 %MOD가 10억 쯤 이어서 3개를 더하면 int 범위가 초과되어 답이 틀리는 부분이었다.

그래서 위에 부분처럼 바꾸었다.

할인행사

import java.util.*;
class Solution {
    Map<String,Integer> countMap = new HashMap<>();
    // Map<String,Integer> curMap = new HashMap<>();
    int totalCount = 0;
    public int solution(String[] want, int[] number, String[] discount) {
        int count = 0;
        for(int i=0 ; i<want.length ; i++){
            countMap.put(want[i], number[i]);
            // curMap.put(want[i], 0);
            totalCount += number[i];
        }
        System.out.println(totalCount);
        for(int i=0 ; i<10 ; i++){
            if(countMap.containsKey(discount[i])){
                countMap.put(discount[i], countMap.get(discount[i]) - 1);
                // System.out.println(":::"+discount[i] + countMap.get(discount[i]));
                if(countMap.get(discount[i]) >=0){
                    totalCount--;
                }
            }
        }
        if(totalCount <= 0) count++;
        
        for(int i=0 ; i<discount.length-10 ; i++){
            int j = i + 10;
            
            if(countMap.containsKey(discount[j])) {
                countMap.put(discount[j], countMap.get(discount[j]) - 1);
                // System.out.println(discount[j] + countMap.get(discount[j]));
                if(countMap.get(discount[j]) >=0){
                    totalCount--;
                }
            }
            if(countMap.containsKey(discount[i])) {
                countMap.put(discount[i], countMap.get(discount[i]) + 1);
                // System.out.println(discount[i-1] + countMap.get(discount[i-1]));
                if(countMap.get(discount[i]) >0){
                    totalCount++;
                }
            }
            if(totalCount <= 0) count++;
            // System.out.println(totalCount);
        }
        
        return count;
    }
}

여기서 다른분들과 다른 부분은 for문 안에서 if(>9) 이런식으로 추가해서 코드수를 줄인 부분이었다.

나는 10개 누적을 먼저 for을 따로 돌렸었다.