[1월 4주차] 이모티콘 할인행사 2023 KAKAO BLIND RECRUITMENT

[eunbc]

필수 문제

이모티콘 할인행사

코드 💻

자율 문제

문제1

코드 💻

문제2

코드 💻

[KarmaPol]

필수 문제

코드

코드 접기/펼치기

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

vector<vector<int>> discounts;

void getdiscounts(int n, vector<int> temp, int stage){
    if(n == stage){
        discounts.push_back(temp);
        return;
    }
    for(int i = 10; i <= 40; i += 10){
        temp.push_back(i);
        getdiscounts(n, temp, stage+1);
        
        temp.pop_back();
    }
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    vector<pair<int, int>> results; 
    
    vector<int> temp;
    getdiscounts(emoticons.size(), temp, 0);
    
    for(auto discount : discounts){
        int tot = 0, plus = 0;
        for(auto user : users){
            int user_discount = user[0];
            int user_price = user[1];
            int temp_price = 0;
            for(int i = 0; i < emoticons.size(); i++){
                if(discount[i] < user_discount) continue;
                
                temp_price += emoticons[i]*(100-discount[i])/100;
                if(temp_price >= user_price){
                    temp_price = 0;
                    plus++;
                    break;
                }
            }
            tot += temp_price;
        }
        results.push_back({plus, tot});
    }

    sort(results.begin(), results.end());
    
    vector<int> answer;
    answer.push_back(results[results.size()-1].first); 
    answer.push_back(results[results.size()-1].second);
    
    return answer;
}

코멘트

완전탐색 + sort + 중복순열
c++ dfs 조합, 순열 정리

자율 문제

카카오 2022 블라인드 - 양과 늑대

코드

코드 접기/펼치기

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> global_info;
vector<vector<int>> routes(20);
int visited[20][20][20];
int counted[20];
int maxs = 0;

void dfs(int current, int sheep, int wolf){
    if(maxs < sheep) maxs = sheep;
    
    for(auto next : routes[current]){
        if(visited[current][next][sheep] == 1) continue;
        int tempsheep = sheep, tempwolf = wolf;
        if(counted[next] == 0){
            if(global_info[next] == 1) tempwolf++;
            else tempsheep++;
        }
        if(tempwolf >= tempsheep) continue;
        
        visited[current][next][sheep] = 1;
        counted[next]++;
        
        dfs(next, tempsheep, tempwolf);
        counted[next]--;
        visited[current][next][sheep] = 0;
    }
}

int solution(vector<int> info, vector<vector<int>> edges) {
    global_info = info;
    
    for(auto edge : edges){
        routes[edge[0]].push_back(edge[1]);
        routes[edge[1]].push_back(edge[0]);
    }
    counted[0]++;   
    dfs(0, 1, 0);
    
    return maxs;
}

코멘트

이진트리탐색 + dfs
현재 상태에 따라 방문 여부를 체크해야한다 -> visited 3중 배열

카카오 2022 블라인드 - 양궁대회

코드

코드 접기/펼치기

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<vector<int>> combinations;

void dfs(vector<int> temp, int n, int stage){
    if(stage == -1){
        combinations.push_back(temp);
        return;
    }
    for(int i = 0; i <= n; i++){
        temp[stage] = i;
        if(stage == 0&& i != n) continue;
        dfs(temp, n-i, stage-1);
    }
}

vector<int> solution(int n, vector<int> info) {
    vector<int> answer;
    
    vector<int> temp(11);
    dfs(temp, n, 10);
    
    int maxscore = 1;
    
    for(auto combination : combinations){
        int tot = 0;
        for(int i = 0; i < 11; i++){
            int currentscore = 10-i;
            
            if(combination[i] > info[i]){
                tot += currentscore;
            }
            else if(info[i] == 0) continue;
            else tot -= currentscore;
        }
        
        if(maxscore <= tot){
            maxscore = tot;
            answer= combination;
        }
    }
    
    if(answer.empty()) answer.push_back(-1);
    
    return answer;
}

코멘트

조합 + 완전탐색
완전탐색 시간복잡도를 줄이고 싶다

[park0jae]

필수 문제

이모티콘 할인행사

코드 💻

import java.util.*;

class Solution {
    
    static int[] discount = new int[] {10,20,30,40};
    static int maxJoin = -1;
    static int maxPrice = -1;
    
    public int[] solution(int[][] users, int[] emoticons) {
        getAllDiscount(0, emoticons.length, new int[emoticons.length], users, emoticons);
        return new int[]{maxJoin, maxPrice};
    }
    
    private void getAllDiscount(int idx, int depth, int[] discountList, int[][] users, int[] emoticons) {
        if (idx == depth) {
            calculatePrice(discountList, users, emoticons);
            return;
        }

        for (int i = 0; i < 4; i++) {
            discountList[idx] = discount[i];
            getAllDiscount(idx + 1, depth, discountList, users, emoticons);
        }
    }
    
    private void calculatePrice(int[] discountList, int[][] users, int[] emoticons) {
        int join = 0;
        int price = 0;
        
        for(int[] user : users) {
            int userMinDiscount = user[0];
            int userMaxPrice = user[1];
            
            int totalPrice = 0;
            
            for(int i=0; i<emoticons.length; i++) {
                if(userMinDiscount <= discountList[i]) {
                    double discountRate = (double) discountList[i] / 100.0;
                    int discountPrice = (int) (emoticons[i] - (emoticons[i] * discountRate));
                    totalPrice += discountPrice; 
                }
            }
            if(totalPrice >= userMaxPrice) {
                join++;
            } else {
                price += totalPrice;
            }
        }
        if(join > maxJoin) {
            maxJoin = join;
            maxPrice = price;
        } else if(join == maxJoin) {
            maxPrice = Math.max(maxPrice, price);
        } 
        return ;
    }
}

자율 문제

백준 3055번: 탈출

코드 💻

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int R,C;
    static char[][] forest;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int count = 0;
    static Queue<int[]> water = new LinkedList<>();
    static Queue<int[]> dochi = new LinkedList<>();
    static int result = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        forest = new char[R][C];

        for(int i=0; i<R; i++) {
            String s = br.readLine();
            for(int j=0; j<C; j++) {
                forest[i][j] = s.charAt(j);
                if(forest[i][j] == 'S') {
                    dochi.add(new int[]{i,j});
                } else if(forest[i][j] == '*') {
                    // 물의 위치
                    water.add(new int[]{i,j});
                }
            }
        }
        bfs();
    }

    public static void bfs() {
        while(true) {
            count++;
            // 홍수 확장 
            moveWater();
            // 고슴도치 이동
            if(arrivedDochi()) break;
        }
    }

    private static void moveWater() {
        int waterSize = water.size();
        for(int i=0; i<waterSize; i++) {
            int[] curWater = water.poll();

            for(int j=0; j<4; j++) {
                int nx = curWater[0] + dx[j];
                int ny = curWater[1] + dy[j];
                
                if(nx < 0 || nx >= R || ny < 0 || ny >= C || forest[nx][ny] != '.') continue;

                forest[nx][ny] = '*';
                water.add(new int[]{nx,ny});
            }
        }
    }

    private static boolean arrivedDochi() {
        int dochiSize = dochi.size();

        if(dochiSize == 0) {
            System.out.println("KAKTUS");
            return true;
        }
        for(int i=0; i<dochiSize; i++) {
            int[] curDochi = dochi.poll();
            
            for(int j=0; j<4; j++) {
                int nx = curDochi[0] + dx[j];
                int ny = curDochi[1] + dy[j];

                if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;

                if(forest[nx][ny] == 'D') {
                    System.out.println(count);
                    return true;
                }
                
                if(forest[nx][ny] != '.') continue;

                forest[nx][ny] = 'S';
                dochi.add(new int[]{nx,ny});
            }
        }
        return false;
    }
}

백준 1931번 : 회의실 배정

코드 💻

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        List<int[]> conference = new ArrayList<>();

        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int startTime = Integer.parseInt(st.nextToken());
            int endTime = Integer.parseInt(st.nextToken());

            conference.add(new int[]{startTime, endTime});
        }

        conference.sort(
            Comparator.comparingInt((int[] arr) -> arr[1])
                .thenComparingInt(arr -> arr[0])
        );
        
        int preEndTime = 0;
        for(int i=0; i<N; i++) {
            if(conference.get(i)[0] >= preEndTime) {
                preEndTime = conference.get(i)[1];
                count++;
            }
        }
        System.out.println(count);
    }
}

[annahxxl]

필수 문제

이모티콘 할인행사

시간 초과..

코드 💻

import java.util.*;

public class Solution {
	static int[][] USERS;
	static int[] EMOTICONS;
	static int totalSubscribers = 0;
	static int totalAmount = 0;

	public int[] solution(int[][] users, int[] emoticons) {
		USERS = users;
		EMOTICONS = emoticons;

		dfs(0, 0, 0, new int[USERS.length], 10);
		dfs(0, 0, 0, new int[USERS.length], 20);
		dfs(0, 0, 0, new int[USERS.length], 30);
		dfs(0, 0, 0, new int[USERS.length], 40);

		return new int[] {totalSubscribers, totalAmount};
	}

	private void dfs(int depth, int curSubscribers, int curAmount, int[] curAmountByUser, int discountRate) {
		if (depth >= EMOTICONS.length) {
			if (curSubscribers > totalSubscribers) {
				totalSubscribers = curSubscribers;
				totalAmount = curAmount;
			} else if (curSubscribers == totalSubscribers) {
				totalAmount = Math.max(totalAmount, curAmount);
			}
			return;
		}

		for (int i = 0; i < USERS.length; i++) {
			if (curAmountByUser[i] == -1) {
				continue;
			}

			int curAmountOfUser = curAmountByUser[i];

			if (USERS[i][0] <= discountRate) {
				int discountPrice = (int)(EMOTICONS[depth] * (100 - discountRate) / 100.0);

				if (curAmountOfUser + discountPrice >= USERS[i][1]) {
					curAmountByUser[i] = -1;
					curSubscribers++;
					curAmount -= curAmountOfUser;
				} else {
					curAmountByUser[i] += discountPrice;
					curAmount += discountPrice;
				}
			}

			dfs(depth + 1, curSubscribers, curAmount, Arrays.copyOf(curAmountByUser, curAmountByUser.length), 10);
			dfs(depth + 1, curSubscribers, curAmount, Arrays.copyOf(curAmountByUser, curAmountByUser.length), 20);
			dfs(depth + 1, curSubscribers, curAmount, Arrays.copyOf(curAmountByUser, curAmountByUser.length), 30);
			dfs(depth + 1, curSubscribers, curAmount, Arrays.copyOf(curAmountByUser, curAmountByUser.length), 40);
		}
	}
}

자율 문제

비밀번호

코드 💻

import java.util.*;

class Solution {
    public int solution(int[] keypad, String password) {
        int[][] pad = new int[3][3];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                pad[i][j] = keypad[i * 3 + j];
            }
        }

        int[][] dis = new int[10][10];
        for (int i = 0; i < 10; i++) {
            Arrays.fill(dis[i], 2);
            dis[i][i] = 0;
        }

        int[][] dir = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                int from = pad[i][j];
                for (int k = 0; k < 8; k++) {
                    int nx = dir[k][0];
                    int ny = dir[k][1];
                    if (i + nx >= 0 && i + nx < 3 && j + ny >= 0 && j + ny < 3) {
                        int to = pad[i + nx][j + ny];
                        dis[from][to] = 1;
                    }
                }
            }
        }

        int answer = 0;
        for (int i = 1; i < password.length(); i++) {
            int from = (int) password.charAt(i - 1) - 48;
            int to = (int) password.charAt(i) - 48;
            answer += dis[from][to];
        }

        return answer;
    }
}

회의실 만남

코드 💻

**

import java.util.*;

class Solution {
    public int[] solution(int[] enter, int[] exit) {
        int n = enter.length;

        for (int i = 0; i < n; i++) {
            enter[i]--;
            exit[i]--;
        }

        int[] enterOrder = new int[n];
        for (int i = 0; i < n; i++) {
            enterOrder[enter[i]] = i;
        }

        int[] enterTime = new int[n];
        int[] exitTime = new int[n];
        int cnt = 0;
        for (int i = 0, j = 0; i < n; i++) {
            while (j < n && j <= enterOrder[exit[i]]) {
                enterTime[enter[j]] = cnt++;
                j++;
            }
            exitTime[exit[i]] = cnt++;
        }

        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (!(exitTime[i] < enterTime[j] || exitTime[j] < enterTime[i])) {
                    answer[i]++;
                    answer[j]++;
                }
            }
        }

        return answer;
    }
}

[byulcode]

필수 문제

이모티콘 할인행사

코드 💻

import java.util.*;

class Solution {

    static int totalSubs, totalCost;
    static int[] discount = {10, 20, 30, 40};

    public int[] solution(int[][] users, int[] emoticons) {
        dfs(0, users, emoticons, new int[emoticons.length]);
        return new int[]{totalSubs, totalCost};
    }

    static void dfs(int idx, int[][]users, int[] emoticons, int[] curDis) {
        int sub = 0;
        int cost = 0;
        if (idx == emoticons.length) {
            for (int i = 0; i < users.length; i++) {
                int sum = 0;
                for (int j = 0; j < emoticons.length; j++) {
                    if (curDis[j] >= users[i][0]) {
                        sum += emoticons[j] * (100 - curDis[j]) / 100;
                    }
                }
                if (sum >= users[i][1]) {
                    sub++;
                } else {
                    cost += sum;
                }
            }
            if (sub > totalSubs) {
                totalSubs = sub;
                totalCost = cost;
            } else if (totalSubs == sub) {
                totalCost = Math.max(totalCost, cost);
            }
        } else {
            for (int i = 0; i < 4; i++) {
                curDis[idx] = discount[i];
                dfs(idx + 1, users, emoticons, curDis);
            }
        }
    }
}

자율 문제

Softeer 징검다리2

코드 💻

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

public class Main {

	static int[] h, dpUp, dpDown;
	static int N, ans;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		h = new int[N];
		dpUp = new int[N];
		dpDown = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			h[i] = Integer.parseInt(st.nextToken());
		}
		dpIncrease();
		dpDecrease();

		for (int i = 0; i < N; i++) {
			ans = Math.max(ans, dpUp[i] + dpDown[i]);
		}

		System.out.println(ans - 1);
	}

	// LIS
	static void dpIncrease() {
		int[] lis = new int[N];
		Arrays.fill(lis, Integer.MAX_VALUE);

		for (int i = 0; i < N; i++) {
			int idx = Arrays.binarySearch(lis, h[i]);
			if (idx < 0) {
				idx = -(idx + 1);
			}
			lis[idx] = h[i];
			dpUp[i] = idx + 1;
		}
	}

	// LDS
	static void dpDecrease() {
		int[] lis = new int[N];
		Arrays.fill(lis, Integer.MAX_VALUE);
		for (int i = N - 1; i >= 0; i--) {
			int idx = Arrays.binarySearch(lis, h[i]);
			if (idx < 0) {
				idx = -(idx + 1);
			}
			lis[idx] = h[i];
			dpDown[i] = idx + 1;
		}
	}
}

백준 숨바꼭질3

코드 💻

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

public class Main {

	static int n, k, ans = Integer.MAX_VALUE;
	static final int MAX_NUM = 100000;
	static boolean[] visited;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		visited = new boolean[MAX_NUM + 1];

		bfs();
		System.out.println(ans);
	}

	static void bfs() {
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] {n, 0});

		while (!queue.isEmpty()) {
			int[] p = queue.poll();
			int x = p[0];
			int t = p[1];
			visited[x] = true;
			if (x == k) {
				ans = Math.min(ans, t);
			}

			if (x * 2 >= 0 && x * 2 <= MAX_NUM && !visited[x * 2])
				queue.add(new int[] {x * 2, t});
			if (x - 1 >= 0 && x - 1 <= MAX_NUM && !visited[x - 1])
				queue.add(new int[] {x - 1, t + 1});
			if (x + 1 >= 0 && x + 1 <= MAX_NUM && !visited[x + 1])
				queue.add(new int[] {x + 1, t + 1});
		}
	}
}

[eunbc]

필수 문제

이모티콘 할인행사

코드 💻

class Solution {
    
    int[] answer = new int[2];
    int[] discount;
    int minDiscount = 100;
    
    public int[] solution(int[][] users, int[] emoticons) {
        discount = new int[emoticons.length];
        
        // 최소 할인율 구하기
        for(int i=0; i<users.length; i++) {
            minDiscount = Math.min(minDiscount, users[i][0]);
        }
        minDiscount = (int) Math.ceil((double) minDiscount/10)*10;
        
        // 할인율 별 판매금액, 서비스 가입자 수 탐색 
        func(0, users, emoticons);
        
        return answer;
    }
    
    void func(int now, int[][] users, int[] emoticons) {
        if(now == emoticons.length) {            
            int[] res = new int[2];
            
            // 할인율별 결과값 집계
            for(int i=0; i<users.length; i++) {
                int price = 0;
                for(int j=0; j<emoticons.length; j++) {
                    if(users[i][0] <= discount[j]) {
                        price += (emoticons[j] * ((double)(100-discount[j])/100));
                    }
                }
                
                if(price >= users[i][1]) res[0]++;
                else res[1] += price;
            }
            
            // 최댓값 집계
            if(res[0]>answer[0]) {
                answer[0] = res[0];
                answer[1] = res[1];
            } else if(res[0]==answer[0]) {
                answer[1] = Math.max(answer[1], res[1]);
            }
            return;
        }
        
        for(int i=minDiscount; i<=40; i=i+10) {
            discount[now] = i;
            func(now + 1, users, emoticons);
        }
    }
}

• 유형 : 완전탐색, DFS
• 부동소수점 오차에 유의하자!

자율 문제

백준 5427 불

코드 💻

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

public class Main { 
    static int t, w, h;
    static char[][] map;
    static int[][] visited;
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,1,0,-1};
    static Queue<Pos> q, fire;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        while(t-->0) {
            int w = sc.nextInt();
            int h = sc.nextInt();

            map = new char[h][w];
            visited = new int[h][w];
            for(int i=0; i<visited.length; i++) {
                Arrays.fill(visited[i], -1);
            }
            q = new LinkedList<>();
            fire = new LinkedList<>();
            boolean check = false;
            
            for(int i=0; i<h; i++) {
                String str = sc.next();
                for(int j=0; j<w; j++) {
                    map[i][j] = str.charAt(j);
                    if(map[i][j]=='*') {
                        fire.offer(new Pos(i,j));
                    }

                    if(map[i][j]=='@') {
                        q.offer(new Pos(i,j));
                        visited[i][j] = 0;
                    }
                }
            }

            out : while(true) {
                // 불 번짐
                int fSize = fire.size();
                for(int i=0; i<fSize; i++) {
                    Pos cur = fire.poll();
                    for(int dir = 0; dir < 4; dir++) {
                        int nx = cur.x + dx[dir];
                        int ny = cur.y + dy[dir];
                        if(nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
                        if(map[nx][ny]=='#' || map[nx][ny]=='*') continue;
                        map[nx][ny] = '*';
                        fire.offer(new Pos(nx, ny));
                    }
                }

                // 상근 이동
                int qSize = q.size();
                for(int i=0; i<qSize; i++) {
                    Pos cur = q.peek(); q.poll();
                    for(int dir=0; dir<4; dir++) {
                        int nx = cur.x + dx[dir];
                        int ny = cur.y + dy[dir];
                        if(nx < 0 || nx >= h || ny < 0 || ny >= w) {
                            sb.append(visited[cur.x][cur.y] + 1 + "\n");
                            check = true;
                            break out;
                        }
                        if(visited[nx][ny]>=0 || map[nx][ny]=='#' || map[nx][ny]=='*') continue;
                        q.offer(new Pos(nx, ny));
                        visited[nx][ny] = visited[cur.x][cur.y] + 1;    
                    }
                }

                if(q.isEmpty()) break;
            }
            
            if(!check) sb.append("IMPOSSIBLE\n");

        }
        System.out.println(sb.toString());
    }

    static class Pos {
        int x;
        int y;
        Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }


}

• 유형 : BFS

백준 1003 피보나치 함수

코드 💻

반복문(Bottom-Up)

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

public class Main { 

    static int[][] dp = new int[45][2];
    public static void main(String[] args) throws IOException {
        // dp 채우기
        dp[0][0] = 1;
        dp[0][1] = 0;
        dp[1][0] = 0;
        dp[1][1] = 1;
        for(int i=2; i<dp.length; i++) {
            dp[i][0] = dp[i-1][0] + dp[i-2][0];
            dp[i][1] = dp[i-1][1] + dp[i-2][1];
        }

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-->0) {
            int N = sc.nextInt();
            System.out.println(dp[N][0] + " " + dp[N][1]);
        }
    }

}

재귀(Top-Down)

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

public class Main { 

    static Integer[][] dp = new Integer[45][2];
    public static void main(String[] args) throws IOException {
        dp[0][0] = 1;
        dp[0][1] = 0;
        dp[1][0] = 0;
        dp[1][1] = 1;

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-->0) {
            int N = sc.nextInt();
            fib(N);
            System.out.println(dp[N][0] + " " + dp[N][1]);
        }
    }

    static Integer[] fib(int n) {
        if(dp[n][0] == null || dp[n][1] == null) {
            dp[n][0] = fib(n-1)[0] + fib(n-2)[0];
            dp[n][1] = fib(n-1)[1] + fib(n-2)[1];
        }
        return dp[n];
    }

}

• 유형 : DP
• 피보나치 수열의 int범위는 46번째까지이다.

[kimday0326]

필수 문제

이모티콘 할인 행사

class Solution {
	private static final int[] PERCENT = {10, 20, 30, 40};

	public int[] solution(int[][] users, int[] emoticons) {
		int[] discount = new int[emoticons.length];
		int[] answer = dfs(0, discount, users, emoticons);
		return answer;
	}

	private int[] dfs(int depth, int[] discount, int[][] users, int[] emoticons) {
		int[] result = new int[2];

		if (depth == emoticons.length) {
			int[] cost = new int[users.length];
			for (int i = 0; i < emoticons.length; i++) {
				for (int j = 0; j < users.length; j++) {
					if (discount[i] >= users[j][0]) {
						cost[j] += (emoticons[i] * (100 - discount[i])) * 0.01;
					}
				}
			}
			for (int i = 0; i < users.length; i++) {
				if (cost[i] >= users[i][1]) {
					result[0]++;
				} else {
					result[1] += cost[i];
				}
			}
			return result;
		}

		for (int i = 0; i < 4; i++) {
			discount[depth] = PERCENT[i];
			int[] temp = dfs(depth + 1, discount, users, emoticons);
			if (temp[0] > result[0]) {
				result = temp;
			} else if (temp[0] == result[0] && temp[1] > result[1]) {
				result = temp;
			}
		}
		return result;
	}
}

선택 문제

병든 나이트 - 1783

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 세로
		int M = Integer.parseInt(st.nextToken()); // 가로

		if (N >= 3 && M >= 7) {
			System.out.println(M - 2);
		} else {
			int res = 0;
			if (N >= 3) {
				for (int i = 1; i <= M; i++) {
					if (i >= 4) {
						System.out.println(4);
						return;
					}
					res += 1;
				}
				System.out.println(res);
			} else {    // 가로로 2칸씩 이동
				if (N == 1) {
					System.out.println(1);
					return;
				} else {
					for (int i = 1; i <= M; i = i + 2) {
						if (i >= 7) {
							System.out.println(4);
							return;
						}
						res += 1;
					}
					System.out.println(res);
				}
			}
		}

	}
}

회의실 배정 - 1931

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		int[][] time = new int[N][2];
		StringTokenizer st;

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			time[i][0] = Integer.parseInt(st.nextToken());
			time[i][1] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(time, new Comparator<int[]>() {

			@Override
			public int compare(int[] t1, int[] t2) {

				if (t1[1] == t2[1]) {
					return t1[0] - t2[0];
				}

				return t1[1] - t2[1];
			}
		});

		int count = 0;
		int prev_endT = 0;

		for (int i = 0; i < N; i++) {

			if (prev_endT <= time[i][0]) {
				prev_endT = time[i][1];
				count++;
			}
		}

		System.out.print(count);
	}
}