99클럽 코테 스터디 22일차 TIL

비기너

문제

2558. Take Gifts From the Richest Pile

# 우선순위 큐

https://leetcode.com/problems/take-gifts-from-the-richest-pile/description/

풀이

가장 선물의 수가 많은 선물 더미에서 선물을 루트개만 남기고 가져가는 것을 k초 반복했을 때 남은 선물의 수를 구하는 문제이다.

가장 큰 선물 더미를 구해야하므로 우선순위 큐로 맥스힙을 구현하여 사용한다.

k회 동안 가장 큰 선물 더미의 선물의 수를 루트개로 만든다.

이후 선물의 합을 리턴한다. 

코드

import java.util.*;

class Solution {
    public long pickGifts(int[] gifts, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int i : gifts)
            pq.add(i);

        while (k-- > 0) 
            pq.add((int)Math.sqrt(pq.poll()));
        
        long ans = 0;
        while (!pq.isEmpty())
            ans += pq.poll();
        return ans;
    }
}

미들러

문제

피로도

#완전탐색

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

풀이

던전의 최소 필요 피로도와 소모 피로도가 주어졌을 때 유저가 탐험할 수 있는 최대 던전 수를 구하는 문제이다.

던전의 개수가 8 이하이므로 던전 탐험이 가능한 경우를 모두 구해서 던전 수가 가장 많은 경우를 반환하면 된다.

코드

class Solution {
    int ans = 0;
    boolean[] visited;
    
    void go(int cnt, int k, int[][] a) {
        ans = Math.max(ans, cnt);
        for (int i = 0; i < a.length; i++) {
            if (!visited[i] && a[i][0] <= k) {
                visited[i] = true;
                go(cnt + 1, k - a[i][1], a);
                visited[i] = false;
            }
        }
    }
    
    public int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];
        go(0, k, dungeons);
        return ans;
    }
}

챌린저

문제

산 모양 타일링

# 동적계획법

https://school.programmers.co.kr/learn/courses/30/lessons/258705

프로그래머스

풀이

특정 모양의 산 모양 도형을 마름모와 정삼각형 타일을 이용해서 채우는 경우의 수를 구하는 문제이다.

타일을 채울 때 왼쪽에서부터 차례대로 채우면서 규칙을 발견한다.

Bottom up 방식의 DP를 사용해서 왼쪽에서부터 타일을 채우는 경우의 수를 카운팅한다.

타일을 채울 때 맨 왼쪽 아래 삼각형이 마름모 타일로 채워졌는지 아니면 정삼각형 타일로 채워졌는지 따라서 다음 스탭의 타일을 채우는 경우의 수가 달라진다.

정삼각형 타일로 채워졌을 때 아래 모양의 마름모로 해당 삼각형과 다음 스탭의 삼각형이 채워지는 경우를 고려한다.

 

 

코드

// d[i][0]: 맨 아래 정삼각형이 정삼각형 타일로 채워짐
// d[i][1]: 맨 아래 정삼각형이 마름모 타일로 채워짐

class Solution {
    public int solution(int n, int[] tops) {
        int[][] d = new int[n + 1][2];
        d[0][0] = 1;
        for (int i = 0; i < n; i++) {
            d[i + 1][1] = (d[i][1] + d[i][0]) % 10007;
            // d[i][0]로 d[i + 1][0]에 합산해줄 경우 
            // 이전 스탭의 오른쪽 아래 삼각형과 이번 스탭의 삼각형이 마름모로 채워지는 경우를 고려
            if (tops[i] == 1)
                d[i + 1][0] = (d[i][0] * 3 + d[i][1] * 2) % 10007;
            else
                d[i + 1][0] = (d[i][0] * 2 + d[i][1]) % 10007;
        }
        
        return (d[n][0] + d[n][1]) % 10007;
    }
}