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

[eunbc]

필수 문제

이모티콘 할인행사

코드 💻

```java ```

[KarmaPol]

필수 문제

코드

코드 접기/펼치기

```c++ #include #include #include #include using namespace std; vector> discounts; void getdiscounts(int n, vector 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 solution(vector> users, vector emoticons) { vector> results; vector 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 answer; answer.push_back(results[results.size()-1].first); answer.push_back(results[results.size()-1].second); return answer; } ```

코멘트

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

자율 문제

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

코드

코드 접기/펼치기

```c++ #include #include #include using namespace std; vector global_info; vector> 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 info, vector> 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 블라인드 - 양궁대회]()

코드

코드 접기/펼치기

```c++ #include #include #include using namespace std; vector> combinations; void dfs(vector 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 solution(int n, vector info) { vector answer; vector 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]

필수 문제

이모티콘 할인행사

코드 💻

```java 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= userMaxPrice) { join++; } else { price += totalPrice; } } if(join > maxJoin) { maxJoin = join; maxPrice = price; } else if(join == maxJoin) { maxPrice = Math.max(maxPrice, price); } return ; } } ```

[annahxxl]

필수 문제

이모티콘 할인행사

시간 초과..

코드 💻

```java 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); } } } ```

[byulcode]

필수 문제

이모티콘 할인행사

코드 💻

```java 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

코드 💻

```java 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

코드 💻

```java 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 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]

필수 문제

이모티콘 할인행사

코드 💻

```java 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[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 불

코드 💻

```java 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 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(); fire = new LinkedList<>(); boolean check = false; for(int i=0; i= 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= 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) ```java 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; i0) { int N = sc.nextInt(); System.out.println(dp[N][0] + " " + dp[N][1]); } } } ``` 재귀(Top-Down) ```java 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]

필수 문제

이모티콘 할인 행사

```java 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

```java 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

```java 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() { @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); } } ```