문제 주소
https://school.programmers.co.kr/learn/courses/30/lessons/150368
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명
카카오톡에서는 이모티콘을 무제한으로 사용할 수 있는 이모티콘 플러스 서비스 가입자 수를 늘리려고 합니다.
이를 위해 카카오톡에서는 이모티콘 할인 행사를 하는데, 목표는 다음과 같습니다.
- 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것.
- 이모티콘 판매액을 최대한 늘리는 것.
1번 목표가 우선이며, 2번 목표가 그 다음입니다.
이모티콘 할인 행사는 다음과 같은 방식으로 진행됩니다.
- n명의 카카오톡 사용자들에게 이모티콘 m개를 할인하여 판매합니다.
- 이모티콘마다 할인율은 다를 수 있으며, 할인율은 10%, 20%, 30%, 40% 중 하나로 설정됩니다.
카카오톡 사용자들은 다음과 같은 기준을 따라 이모티콘을 사거나, 이모티콘 플러스 서비스에 가입합니다.
- 각 사용자들은 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘을 모두 구매합니다.
- 각 사용자들은 자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 된다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.
다음은 2명의 카카오톡 사용자와 2개의 이모티콘이 있을때의 예시입니다.
사용자 비율 가격
| 1 | 40 | 10,000 |
| 2 | 25 | 10,000 |
이모티콘 가격
| 1 | 7,000 |
| 2 | 9,000 |
1번 사용자는 40%이상 할인하는 이모티콘을 모두 구매하고, 이모티콘 구매 비용이 10,000원 이상이 되면 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.
2번 사용자는 25%이상 할인하는 이모티콘을 모두 구매하고, 이모티콘 구매 비용이 10,000원 이상이 되면 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.
1번 이모티콘의 가격은 7,000원, 2번 이모티콘의 가격은 9,000원입니다.
만약, 2개의 이모티콘을 모두 40%씩 할인한다면, 1번 사용자와 2번 사용자 모두 1,2번 이모티콘을 구매하게 되고, 결과는 다음과 같습니다.
사용자 구매한 이모티콘 이모티콘 구매 비용 이모티콘 플러스 서비스 가입 여부
| 1 | 1, 2 | 9,600 | X |
| 2 | 1, 2 | 9,600 | X |
이모티콘 플러스 서비스 가입자는 0명이 늘어나고 이모티콘 판매액은 19,200원이 늘어납니다.
하지만, 1번 이모티콘을 30% 할인하고 2번 이모티콘을 40% 할인한다면 결과는 다음과 같습니다.
사용자 구매한 이모티콘 이모티콘 구매 비용 이모티콘 플러스 서비스 가입 여부
| 1 | 2 | 5,400 | X |
| 2 | 1, 2 | 10,300 | O |
2번 사용자는 이모티콘 구매 비용을 10,000원 이상 사용하여 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입하게 됩니다.
따라서, 이모티콘 플러스 서비스 가입자는 1명이 늘어나고 이모티콘 판매액은 5,400원이 늘어나게 됩니다.
카카오톡 사용자 n명의 구매 기준을 담은 2차원 정수 배열 users, 이모티콘 m개의 정가를 담은 1차원 정수 배열 emoticons가 주어집니다. 이때, 행사 목적을 최대한으로 달성했을 때의 이모티콘 플러스 서비스 가입 수와 이모티콘 매출액을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤ users의 길이 = n ≤ 100
- users의 원소는 [비율, 가격]의 형태입니다.
- users[i]는 i+1번 고객의 구매 기준을 의미합니다.
- 비율% 이상의 할인이 있는 이모티콘을 모두 구매한다는 의미입니다.
- 1 ≤ 비율 ≤ 40
- 가격이상의 돈을 이모티콘 구매에 사용한다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입한다는 의미입니다.
- 100 ≤ 가격 ≤ 1,000,000
- 가격은 100의 배수입니다.
- 1 ≤ emoticons의 길이 = m ≤ 7
- emoticons[i]는 i+1번 이모티콘의 정가를 의미합니다.
- 100 ≤ emoticons의 원소 ≤ 1,000,000
- emoticons의 원소는 100의 배수입니다.
입출력 예
users emoticons result
| [[40, 10000], [25, 10000]] | [7000, 9000] | [1, 5400] |
| [[40, 2900], [23, 10000], [11, 5200], [5, 5900], [40, 3100], [27, 9200], [32, 6900]] | [1300, 1500, 1600, 4900] | [4, 13860] |
입출력 예 설명
입출력 예 #1
문제의 예시와 같습니다.
입출력 예 #2
다음과 같이 할인하는 것이 이모티콘 플러스 서비스 가입자를 최대한 늘리면서, 이모티콘 판매액 또한 최대로 늘리는 방법입니다.
이모티콘 할인율
| 1 | 40 |
| 2 | 40 |
| 3 | 20 |
| 4 | 40 |
위와 같이 할인하면 4명의 이모티콘 플러스 가입자와 13,860원의 판매액을 달성할 수 있습니다. 다른 할인율을 적용하여 이모티콘을 판매할 수 있지만 이보다 이모티콘 플러스 서비스 가입자를 최대한 늘리면서, 이모티콘 판매액 또한 최대로 늘리는 방법은 없습니다.
따라서, [4, 13860]을 return 하면 됩니다.
- 각 사용자들은 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘을 모두 구매합니다.
- 각 사용자들은 자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 된다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.
제출 코드
import java.util.*;
class Solution {
int [][] user;
int [] emoticon;
int maxPlus = 0;
int maxCost = 0;
int maxDiscount = 40;
public int[] solution(int[][] users, int[] emoticons) {
user = users;
emoticon = emoticons;
//백트래킹 느낌으로 하자~~
int [] discount = new int[emoticon.length];
search(discount,0);
int[] answer = {maxPlus,maxCost};//이모티콘 플러스 서비스 가입 수와 이모티콘 매출액
return answer;
}
public void search(int [] discount, int depth){
//할인율 점점 올려보면서 이모티콘플러스 가입자수가 max가 될때 매출액 update하는 걸로 풀면 될듯함
if(depth>=emoticon.length){
return;
}
for(int j=0;j<=40;j+=10){
int [] temp = discount.clone();
temp[depth] = temp[depth]+j;
calculate(temp);
search(temp, depth+1);
}
}
public void calculate(int [] discount){
int people = 0;
int money = 0;
for(int u = 0; u<user.length; u++){
int sum = 0;
for(int i=0;i<discount.length;i++){
if(user[u][0]<=discount[i]){
int plus = emoticon[i]*(100-discount[i])/100;
sum += plus;
}
}
if(sum>=user[u][1]){
people++;//이모티콘을 구독하면 비용 발생 x
}else{
money += sum;
}
}
if(people>maxPlus){
maxPlus = people;
maxCost = money;
}else if(people == maxPlus){
if(money>maxCost){
maxCost = money;
}
}
}
}
코드 설명
백트래킹 느낌으로 풀었다
할인율 배열을 가지고 가서 계산해서 가입자수가 최대 -> 판매금액이 높은 기준으로 저장함
depth(할인율 배열의 인덱스)의 할인율을 10,20,30,40으로 바꾸면서 돌려봄
풀이과정
일단 백트래킹 느끼믕로 이렇게 짜봄
import java.util.*;
class Solution {
int [][] user;
int [] emoticon;
int maxPlus = 0;
int maxCost = 0;
int maxDiscount = 40;
public int[] solution(int[][] users, int[] emoticons) {
user = users;
emoticon = emoticons;
//백트래킹 느낌으로 하자~~
int [] discount = new int[emoticon.length];
search(discount,0);
int[] answer = {maxPlus,maxCost};//이모티콘 플러스 서비스 가입 수와 이모티콘 매출액
return answer;
}
public void search(int [] discount, int depth){
//할인율 점점 올려보면서 이모티콘플러스 가입자수가 max가 될때 매출액 update하는 걸로 풀면 될듯함
if(depth>=emoticon.length){
return;
}
calculate(discount);
for(int j=0;j<=40;j+=10){
int [] temp = discount.clone();
temp[depth] = temp[depth]+j;
search(temp, depth+1);
}
}
public void calculate(int [] discount){
int people = 0;
int money = 0;
//people과 money 계산 로직~~
for(int u = 0; u<user.length; u++){
int sum = 0;
for(int i=0;i<discount.length;i++){
if(user[u][0]<=discount[i]){
money += emoticon[i]*(100-discount[i])/1000;
}
}
if(sum>=user[u][1]){
people++;//이모티콘을 구독하면 비용 발생 x
}else{
money += sum;
}
}
if(people>maxPlus){
maxPlus = people;
maxCost = money;
}else if(people == maxPlus){
if(money>maxCost){
money = maxCost;
}
}
}
}
테스트 1
입력값 〉 [[40, 10000], [25, 10000]], [7000, 9000]
기댓값 〉 [1, 5400]
실행 결과 〉 실행한 결괏값 [0,0]이 기댓값 [1,5400]과 다릅니다.
테스트 2
입력값 〉 [[40, 2900], [23, 10000], [11, 5200], [5, 5900], [40, 3100], [27, 9200], [32, 6900]], [1300, 1500, 1600, 4900]
기댓값 〉 [4, 13860]
실행 결과 〉 실행한 결괏값 [0,0]이 기댓값 [4,13860]과 다릅니다.
0,0이 나와버림~
로그찍어봄
0번 임티 user1의 할인율25 실제 할인율30
money++490
1번 임티 user1의 할인율25 실제 할인율0
0번 임티 user0의 할인율40 실제 할인율40
money++420
1번 임티 user0의 할인율40 실제 할인율0
0번 임티 user1의 할인율25 실제 할인율40
money++420
1번 임티 user1의 할인율25 실제 할인율0
머리로 sum이라고 생각하고 손으로 money라고 쓴 부분 바꿔줌
public void calculate(int [] discount){
int people = 0;
int money = 0;
//people과 money 계산 로직~~
for(int u = 0; u<user.length; u++){
int sum = 0;
for(int i=0;i<discount.length;i++){
System.out.println(i+"번 임티 user"+u+"의 할인율"+user[u][0]+" 실제 할인율"+discount[i]);
if(user[u][0]<=discount[i]){
int plus = emoticon[i]*(100-discount[i])/1000;
System.out.println("money++"+plus);
money += plus;//->여기를 sum으로 해야하는데 money로 함...
}
}
if(sum>=user[u][1]){
people++;//이모티콘을 구독하면 비용 발생 x
}else{
money += sum;
}
}
→
public void calculate(int [] discount){
int people = 0;
int money = 0;
//people과 money 계산 로직~~
for(int u = 0; u<user.length; u++){
int sum = 0;
for(int i=0;i<discount.length;i++){
System.out.println(i+"번 임티 user"+u+"의 할인율"+user[u][0]+" 실제 할인율"+discount[i]);
if(user[u][0]<=discount[i]){
int plus = emoticon[i]*(100-discount[i])/1000;
System.out.println("money++"+plus);
sum += plus;
}
}
if(sum>=user[u][1]){
people++;//이모티콘을 구독하면 비용 발생 x
}else{
money += sum;
}
}
로그찍어봄
public void calculate(int [] discount){
int people = 0;
int money = 0;
//people과 money 계산 로직~~
for(int u = 0; u<user.length; u++){
int sum = 0;
for(int i=0;i<discount.length;i++){
if(user[u][0]<=discount[i]){
System.out.println(i+"번 임티 user"+u+"의 할인율"+user[u][0]+" 실제 할인율"+discount[i]);
int plus = emoticon[i]*(100-discount[i])/1000;
System.out.println("money++"+plus);
sum += plus;
}
}
if(sum>=user[u][1]){
people++;//이모티콘을 구독하면 비용 발생 x
}else{
money += sum;
}
}
System.out.println("구독"+people+" 돈"+money);
if(people>maxPlus){
maxPlus = people;
maxCost = money;
}else if(people == maxPlus){
if(money>maxCost){
money = maxCost;
}
}
}
구독0 돈0
0의 할인율0
구독0 돈0
1의 할인율0
1의 할인율10
1의 할인율20
1의 할인율30
1의 할인율40
0의 할인율10
구독0 돈0
1의 할인율0
1의 할인율10
1의 할인율20
1의 할인율30
1의 할인율40
0의 할인율20
구독0 돈0
1의 할인율0
1의 할인율10
1의 할인율20
1의 할인율30
1의 할인율40
0의 할인율30
0번 임티 user1의 할인율25 실제 할인율30
money++490
구독0 돈490
1의 할인율0
1의 할인율10
1의 할인율20
1의 할인율30
1의 할인율40
0의 할인율40
0번 임티 user0의 할인율40 실제 할인율40
money++420
0번 임티 user1의 할인율25 실제 할인율40
money++420
구독0 돈840
1의 할인율0
1의 할인율10
1의 할인율20
1의 할인율30
1의 할인율40
System.out.println("구독"+people+" 돈"+money);
if(people>maxPlus){
maxPlus = people;
maxCost = money;
}else if(people == maxPlus){
if(money>maxCost){
money = maxCost;
}
}
값이 틀리더라도 저렇게 하면 업데이트는 되어야 하는거 아닌가… 왜 안 찍히지…
System.out.println("구독"+people+" 돈"+money);
if(people>maxPlus){
maxPlus = people;
maxCost = money;
}else if(people == maxPlus){
if(money>maxCost){
money = maxCost;
}
}
System.out.println("maxPlus"+maxPlus+" maxCost"+maxCost);
테스트 2
입력값 〉 [[40, 2900], [23, 10000], [11, 5200], [5, 5900], [40, 3100], [27, 9200], [32, 6900]], [1300, 1500, 1600, 4900]
기댓값 〉 [4, 13860]
실행 결과 〉 실행한 결괏값 [0,0]이 기댓값 [4,13860]과 다릅니다.
출력 〉 구독0 돈0
maxPlus0 maxCost0
구독0 돈0
maxPlus0 maxCost0
구독0 돈0
maxPlus0 maxCost0
구독0 돈0
maxPlus0 maxCost0
구독0 돈144
maxPlus0 maxCost0
구독0 돈256
maxPlus0 maxCost0
구독0 돈448
maxPlus0 maxCost0
구독0 돈672
maxPlus0 maxCost0
구독0 돈135
maxPlus0 maxCost0
구독0 돈135
maxPlus0 maxCost0
구독0 돈279
maxPlus0 maxCost0
구독0 돈391
maxPlus0 maxCost0
구독0 돈583
maxPlus0 maxCost0
구독0 돈807
maxPlus0 maxCost0
구독0 돈240
maxPlus0 maxCost0
구독0 돈240
maxPlus0 maxCost0
...
구독0 돈966
maxPlus0 maxCost0
구독0 돈966
maxPlus0 maxCost0
구독0 돈1110
maxPlus0 maxCost0
구독0 돈1222
maxPlus0 maxCost0
구독0 돈1414
maxPlus0 maxCost0
구독0 돈1638
maxPlus0 maxCost0
구독0 돈1176
maxPlus0 maxCost0
구독0 돈1176
maxPlus0 maxCost0
구독0 돈1320
maxPlus0 maxCost0
구독0 돈1432
maxPlus0 maxCost0
구독0 돈1624
maxPlus0 maxCost0
구독0 돈1848
maxPlus0 maxCost0
엥 업데이트가 안 됨 왜지…
여기도 순서 실수해놔서 다시 바꿔줌
if(money>maxCost){
money = maxCost;
}
→
if(money>maxCost){
maxCost = money;
}
오 이제 돈은 업데이트가 되는데 구독이 안 늘어나…
구독0 돈1848
maxPlus0 maxCost1848
로그를 더 찍어보니 뭔가 지금 돈 단위랑 계산이 이상해서 안 되는 것 같다
490>=10000
420>=10000
420>=10000
380>=5900
0>=3100
0>=9200
0>=6900
할인율10 원래 가격1600계산된 값1440
할인율20 원래 가격1600계산된 값1280
할인율20 원래 가격1600계산된 값1280
할인율30 원래 가격1600계산된 값1120
할인율30 원래 가격1600계산된 값1120
할인율30 원래 가격1600계산된 값1120
for(int i=0;i<discount.length;i++){
if(user[u][0]<=discount[i]){
//System.out.println(i+"번 임티 user"+u+"의 할인율"+user[u][0]+" 실제 할인율"+discount[i]);
int plus = emoticon[i]*(100-discount[i])/100;
System.out.println("할인율"+discount[i]+" 원래 가격"+emoticon[i]+"계산된 값"+plus);
//System.out.println("money++"+plus);
sum += plus;
}
}
유저0 0>=10000
할인율30 원래 가격7000계산된 값4900
유저1 4900>=10000
할인율40 원래 가격7000계산된 값4200
유저0 4200>=10000
할인율40 원래 가격7000계산된 값4200
유저1 4200>=10000
하아 로그 찍어봤는데 안되네~~
sum이 왜 저것밖에 안 나오지??
for(int j=0;j<=40;j+=10){
int [] temp = discount.clone();
System.out.println(depth+"의 할인율"+j);//이 로직은 똑바로 돌고있다!
temp[depth] = temp[depth]+j;
search(temp, depth+1);
}
이렇게 찍고
for(int u = 0; u<user.length; u++){
int sum = 0;
for(int i=0;i<discount.length;i++){
if(user[u][0]<=discount[i]){
//System.out.println(i+"번 임티 user"+u+"의 할인율"+user[u][0]+" 실제 할인율"+discount[i]);
int plus = emoticon[i]*(100-discount[i])/100;
//System.out.println("할인율"+discount[i]+" 원래 가격"+emoticon[i]+"계산된 값"+plus);
//System.out.println("money++"+plus);
sum += plus;
}
}
System.out.println("유저"+u+" "+sum+">="+user[u][1]);
if(sum>=user[u][1]){
people++;//이모티콘을 구독하면 비용 발생 x
}else{
money += sum;
}
}
이렇게 찍었는데 왜 이렇게 나오지
유저0 0>=10000
유저1 0>=10000
0의 할인율0
유저0 0>=10000
유저1 0>=10000
1의 할인율0
1의 할인율10
1의 할인율20
1의 할인율30
1의 할인율40
0의 할인율10
유저0 0>=10000
유저1 0>=10000
1의 할인율0
1의 할인율10
1의 할인율20
1의 할인율30
1의 할인율40
0의 할인율20
유저0 0>=10000
유저1 0>=10000
1의 할인율0
1의 할인율10
1의 할인율20
1의 할인율30
1의 할인율40
0의 할인율30
유저0 0>=10000
유저1 4900>=10000
1의 할인율0
1의 할인율10
1의 할인율20
1의 할인율30
1의 할인율40
0의 할인율40
유저0 4200>=10000
유저1 4200>=10000
1의 할인율0
1의 할인율10
1의 할인율20
1의 할인율30
1의 할인율40
import java.util.*;
class Solution {
int [][] user;
int [] emoticon;
int maxPlus = 0;
int maxCost = 0;
int maxDiscount = 40;
public int[] solution(int[][] users, int[] emoticons) {
user = users;
emoticon = emoticons;
//백트래킹 느낌으로 하자~~
int [] discount = new int[emoticon.length];
search(discount,0);
int[] answer = {maxPlus,maxCost};//이모티콘 플러스 서비스 가입 수와 이모티콘 매출액
return answer;
}
public void search(int [] discount, int depth){
//할인율 점점 올려보면서 이모티콘플러스 가입자수가 max가 될때 매출액 update하는 걸로 풀면 될듯함
if(depth>=emoticon.length){
return;
}
for(int j=0;j<=40;j+=10){
int [] temp = discount.clone();
System.out.println(depth+"의 할인율"+j);
temp[depth] = temp[depth]+j;
calculate(temp);
search(temp, depth+1);
}
}
public void calculate(int [] discount){
int people = 0;
int money = 0;
for(int u = 0; u<user.length; u++){
int sum = 0;
for(int i=0;i<discount.length;i++){
if(user[u][0]<=discount[i]){
//System.out.println(i+"번 임티 user"+u+"의 할인율"+user[u][0]+" 실제 할인율"+discount[i]);
int plus = emoticon[i]*(100-discount[i])/100;
//System.out.println("할인율"+discount[i]+" 원래 가격"+emoticon[i]+"계산된 값"+plus);
//System.out.println("money++"+plus);
sum += plus;
}
}
System.out.println("유저"+u+" "+sum+">="+user[u][1]);
if(sum>=user[u][1]){
people++;//이모티콘을 구독하면 비용 발생 x
}else{
money += sum;
}
}
if(people>maxPlus){
maxPlus = people;
maxCost = money;
}else if(people == maxPlus){
if(money>maxCost){
maxCost = money;
}
}
}
}visit도 안에다 넣어야만 되잖아
✨ calculate 재귀 위치 바꿔주고 성공~~ ✨
public void search(int [] discount, int depth){
//할인율 점점 올려보면서 이모티콘플러스 가입자수가 max가 될때 매출액 update하는 걸로 풀면 될듯함
if(depth>=emoticon.length){
return;
}
calculate(discount);
for(int j=0;j<=40;j+=10){
int [] temp = discount.clone();
System.out.println(depth+"의 할인율"+j);
temp[depth] = temp[depth]+j;
search(temp, depth+1); //-> 이거 들어가서 왜 안 돌아가지? System.out.println("유저"+u+" "+sum+">="+user[u][1]); 이게 호출이 안 되는데 1일때?
}
}
→
public void search(int [] discount, int depth){
//할인율 점점 올려보면서 이모티콘플러스 가입자수가 max가 될때 매출액 update하는 걸로 풀면 될듯함
if(depth>=emoticon.length){
return;
}
for(int j=0;j<=40;j+=10){
int [] temp = discount.clone();
System.out.println(depth+"의 할인율"+j);
temp[depth] = temp[depth]+j;
calculate(temp);
search(temp, depth+1);
}
}
🔎왜 Caculate를 재귀 한 번 더 넘기기 전에 써야만 하는가?
어차피 바로 아랫줄에서 재귀로 넘어가서 계산할건데 왜 재귀 넘기기 전에 계산해야만 맞는지 생각해 보았음
calculate를 재귀를 넘긴 다음에 호출함 : 할인율이 0일때만 calculate가 호출됨
calculate를 재귀를 넘기기 전에 호출함: 모든 할인율에서 calculate가 잘 호출됨
calculate를 재귀를 넘긴 다음에 계산함:
import java.util.*;
class Solution {
int [][] user;
int [] emoticon;
int maxPlus = 0;
int maxCost = 0;
int maxDiscount = 40;
public int[] solution(int[][] users, int[] emoticons) {
user = users;
emoticon = emoticons;
//백트래킹 느낌으로 하자~~
int [] discount = new int[emoticon.length];
search(discount,0);
int[] answer = {maxPlus,maxCost};//이모티콘 플러스 서비스 가입 수와 이모티콘 매출액
return answer;
}
public void search(int [] discount, int depth){
//할인율 점점 올려보면서 이모티콘플러스 가입자수가 max가 될때 매출액 update하는 걸로 풀면 될듯함
if(depth>=emoticon.length){
return;
}
calculate(discount);
for(int j=0;j<=40;j+=10){
int [] temp = discount.clone();
System.out.println(depth+"의 할인율"+j);
temp[depth] = temp[depth]+j;
search(temp, depth+1);
}
}
public void calculate(int [] discount){
int people = 0;
int money = 0;
for(int u = 0; u<user.length; u++){
int sum = 0;
for(int i=0;i<discount.length;i++){
if(user[u][0]<=discount[i]){
//System.out.println(i+"번 임티 user"+u+"의 할인율"+user[u][0]+" 실제 할인율"+discount[i]);
int plus = emoticon[i]*(100-discount[i])/100;
//System.out.println("할인율"+discount[i]+" 원래 가격"+emoticon[i]+"계산된 값"+plus);
//System.out.println("money++"+plus);
sum += plus;
}
}
System.out.println("유저"+u+" "+sum+">="+user[u][1]);
if(sum>=user[u][1]){
people++;//이모티콘을 구독하면 비용 발생 x
}else{
money += sum;
}
}
if(people>maxPlus){
maxPlus = people;
maxCost = money;
}else if(people == maxPlus){
if(money>maxCost){
maxCost = money;
}
}
}
}
유저0 0>=10000
유저1 0>=10000
0의 할인율0
유저0 0>=10000
유저1 0>=10000
1의 할인율0
1의 할인율10 -> calculate에 안 들어가서 유저0 문이 안 찍힘
1의 할인율20-> calculate에 안 들어가서 유저0 문이 안 찍힘
1의 할인율30-> calculate에 안 들어가서 유저0 문이 안 찍힘
1의 할인율40-> calculate에 안 들어가서 유저0 문이 안 찍힘
0의 할인율10-> calculate에 안 들어가서 유저0 문이 안 찍힘
유저0 0>=10000
유저1 0>=10000
1의 할인율0
1의 할인율10-> calculate에 안 들어가서 유저0 문이 안 찍힘
1의 할인율20-> calculate에 안 들어가서 유저0 문이 안 찍힘
1의 할인율30-> calculate에 안 들어가서 유저0 문이 안 찍힘
1의 할인율40-> calculate에 안 들어가서 유저0 문이 안 찍힘
0의 할인율20
유저0 0>=10000
유저1 0>=10000
1의 할인율0
1의 할인율10
1의 할인율20
1의 할인율30
1의 할인율40
0의 할인율30
유저0 0>=10000
유저1 4900>=10000
1의 할인율0
1의 할인율10
1의 할인율20
1의 할인율30
1의 할인율40
0의 할인율40
유저0 4200>=10000
유저1 4200>=10000
1의 할인율0
1의 할인율10
1의 할인율20
1의 할인율30
1의 할인율40
할인율 0일때만 calculate가 돌아감
밑의 테스트케이스도 할인율 0일때만 돌아감
유저0 0>=2900
유저1 0>=10000
유저2 0>=5200
유저3 0>=5900
유저4 0>=3100
유저5 0>=9200
유저6 0>=6900
0의 할인율0
유저0 0>=2900
유저1 0>=10000
유저2 0>=5200
유저3 0>=5900
유저4 0>=3100
유저5 0>=9200
유저6 0>=6900
1의 할인율0
유저0 0>=2900
유저1 0>=10000
유저2 0>=5200
유저3 0>=5900
유저4 0>=3100
유저5 0>=9200
유저6 0>=6900
2의 할인율0
유저0 0>=2900
유저1 0>=10000
유저2 0>=5200
유저3 0>=5900
유저4 0>=3100
유저5 0>=9200
유저6 0>=6900
3의 할인율0
3의 할인율10
3의 할인율20
3의 할인율30
3의 할인율40
2의 할인율10
유저0 0>=2900
유저1 0>=10000
유저2 0>=5200
유저3 1440>=5900
유저4 0>=3100
유저5 0>=9200
유저6 0>=6900
3의 할인율0
3의 할인율10
3의 할인율20
3의 할인율30
3의 할인율40
2의 할인율20
유저0 0>=2900
유저1 0>=10000
유저2 1280>=5200
유저3 1280>=5900
유저4 0>=3100
유저5 0>=9200
유저6 0>=6900
3의 할인율0
3의 할인율10
3의 할인율20
3의 할인율30
3의 할인율40
2의 할인율30
유저0 0>=2900
유저1 1120>=10000
유저2 1120>=5200
유저3 1120>=5900
유저4 0>=3100
유저5 1120>=9200
유저6 0>=6900
3의 할인율0
3의 할인율10
3의 할인율20
3의 할인율30
3의 할인율40
2의 할인율40
유저0 960>=2900
유저1 960>=10000
유저2 960>=5200
유저3 960>=5900
유저4 960>=3100
유저5 960>=9200
유저6 960>=6900
3의 할인율0
3의 할인율10
3의 할인율20
3의 할인율30
3의 할인율40
1의 할인율10
유저0 0>=2900
유저1 0>=10000
유저2 0>=5200
유저3 1350>=5900
유저4 0>=3100
유저5 0>=9200
유저6 0>=6900
2의 할인율0
유저0 0>=2900
유저1 0>=10000
유저2 0>=5200
유저3 1350>=5900
유저4 0>=3100
유저5 0>=9200
유저6 0>=6900
3의 할인율0
3의 할인율10
3의 할인율20
3의 할인율30
3의 할인율40
2의 할인율10
유저0 0>=2900
유저1 0>=10000
유저2 0>=5200
유저3 2790>=5900
유저4 0>=3100
유저5 0>=9200
유저6 0>=6900
3의 할인율0
3의 할인율10
3의 할인율20
3의 할인율30
3의 할인율40
2의 할인율20
유저0 0>=2900
유저1 0>=10000
유저2 1280>=5200
유저3 2630>=5900
유저4 0>=3100
유저5 0>=9200
유저6 0>=6900
3의 할인율0
3의 할인율10
3의 할인율20
3의 할인율30
반면
calculate를 재귀 전에 해주는 경우
import java.util.*;
class Solution {
int [][] user;
int [] emoticon;
int maxPlus = 0;
int maxCost = 0;
int maxDiscount = 40;
public int[] solution(int[][] users, int[] emoticons) {
user = users;
emoticon = emoticons;
//백트래킹 느낌으로 하자~~
int [] discount = new int[emoticon.length];
search(discount,0);
int[] answer = {maxPlus,maxCost};//이모티콘 플러스 서비스 가입 수와 이모티콘 매출액
return answer;
}
public void search(int [] discount, int depth){
//할인율 점점 올려보면서 이모티콘플러스 가입자수가 max가 될때 매출액 update하는 걸로 풀면 될듯함
if(depth>=emoticon.length){
return;
}
for(int j=0;j<=40;j+=10){
int [] temp = discount.clone();
System.out.println(depth+"의 할인율"+j);
temp[depth] = temp[depth]+j;
calculate(discount);
search(temp, depth+1);
}
}
public void calculate(int [] discount){
int people = 0;
int money = 0;
for(int u = 0; u<user.length; u++){
int sum = 0;
for(int i=0;i<discount.length;i++){
if(user[u][0]<=discount[i]){
//System.out.println(i+"번 임티 user"+u+"의 할인율"+user[u][0]+" 실제 할인율"+discount[i]);
int plus = emoticon[i]*(100-discount[i])/100;
//System.out.println("할인율"+discount[i]+" 원래 가격"+emoticon[i]+"계산된 값"+plus);
//System.out.println("money++"+plus);
sum += plus;
}
}
System.out.println("유저"+u+" "+sum+">="+user[u][1]);
if(sum>=user[u][1]){
people++;//이모티콘을 구독하면 비용 발생 x
}else{
money += sum;
}
}
if(people>maxPlus){
maxPlus = people;
maxCost = money;
}else if(people == maxPlus){
if(money>maxCost){
maxCost = money;
}
}
}
}
0의 할인율0
유저0 0>=10000
유저1 0>=10000
1의 할인율0
유저0 0>=10000
유저1 0>=10000
1의 할인율10
유저0 0>=10000
유저1 0>=10000
1의 할인율20
유저0 0>=10000
유저1 0>=10000
1의 할인율30
유저0 0>=10000
유저1 0>=10000
1의 할인율40
유저0 0>=10000
유저1 0>=10000
0의 할인율10
유저0 0>=10000
유저1 0>=10000
1의 할인율0
유저0 0>=10000
유저1 0>=10000
1의 할인율10
유저0 0>=10000
유저1 0>=10000
1의 할인율20
유저0 0>=10000
유저1 0>=10000
1의 할인율30
유저0 0>=10000
유저1 0>=10000
1의 할인율40
유저0 0>=10000
유저1 0>=10000
0의 할인율20
유저0 0>=10000
유저1 0>=10000
1의 할인율0
유저0 0>=10000
유저1 0>=10000
1의 할인율10
유저0 0>=10000
유저1 0>=10000
1의 할인율20
유저0 0>=10000
유저1 0>=10000
1의 할인율30
유저0 0>=10000
유저1 0>=10000
1의 할인율40
유저0 0>=10000
유저1 0>=10000
0의 할인율30
유저0 0>=10000
유저1 0>=10000
1의 할인율0
유저0 0>=10000
유저1 4900>=10000
1의 할인율10
유저0 0>=10000
유저1 4900>=10000
1의 할인율20
유저0 0>=10000
유저1 4900>=10000
1의 할인율30
유저0 0>=10000
유저1 4900>=10000
1의 할인율40
유저0 0>=10000
유저1 4900>=10000
0의 할인율40
유저0 0>=10000
유저1 0>=10000
1의 할인율0
유저0 4200>=10000
유저1 4200>=10000
1의 할인율10
유저0 4200>=10000
유저1 4200>=10000
1의 할인율20
유저0 4200>=10000
유저1 4200>=10000
1의 할인율30
유저0 4200>=10000
유저1 4200>=10000
1의 할인율40
유저0 4200>=10000
유저1 4200>=10000
할인율마다 calculate가 다 찍힘
'Coding Test' 카테고리의 다른 글
| [프로그래머스] 스킬 트리 (0) | 2024.05.21 |
|---|---|
| [프로그래머스] 방문 길이 Java (0) | 2024.05.17 |
| [백준] 나무 자르기 (0) | 2024.04.16 |
| [백준] 예산 (0) | 2024.04.16 |
| [백준] 세탁소 사장 동혁 (0) | 2024.04.16 |
