KiTFOx's Notepad 📝

1. 문제 요약

절댓값이 10c 형태인 정수들이 적힌 버튼
현재 층 수에 버튼에 적혀 있는 값을 더한 층으로 이동
엘리베이터가 위치해 있는 층과 버튼의 값을 더한 결과가 0보다 작으면 엘리베이터는 움직이지 않음
0층이 가장 아래층
버튼 한번 당 돌 한개
최소한의 돌 최대한으로 내려가기
10단위로 나머지 계산
2,5,5,4 -> 16
1,6 -> 1+(10-6) = 5
7~9 인 경우 반올림해서 빼는 경우가 더 이득
1~5 인 경우 그냥 빼는 경우가 이득
2000 + 500 + 50 + 4
작은 결과들을 모아서 큰 결과 값을 만들 수 있는지 확인해보기

2. 코드

#include <string>
#include <vector>

using namespace std;

//최적의 사용 돌 갯수 구해서 answer에 더해주는 함수
void GetOptimalStoneCount(int& storey,int& answer){
    int count = storey%10;
    
    if(count<5) answer+=count;
    else{
        if(count==5&&storey%100<50){
            answer+=count;
        }
        else{
            answer+=10-count;
            storey=storey+10-count;
        }
    }
    storey/=10;
    //printf("%d, %d\n",storey,answer);
}

int solution(int storey) {
    int answer = 0;

    while(storey>1){
        GetOptimalStoneCount(storey,answer);
    }
    
    return answer+storey;
}

3. 해설

제가 선택한 알고리즘의 방법은 10씩 나눈다음 해당 값이 반올림이 가능한지 아닌지를 판별하는 것을 채택했습니다.

예를 들어, 맨 끝의 자리 숫자가 6이상인 경우 -6을 통해 6번 돌을 사용하는 것보다 한자릿수를 늘려서 처리하는 것이 이득입니다. 56의 경우 5+6 = 11 보다 4+6 = 10 의 경우 1의 이득을 더 볼 수 있습니다.

이러한 로직을 바탕으로 코드를 짜게 되면 최적의 돌을 구할 수 있습니다.

다만 5의 경우 주의해야할 점이 555, 545 이 경우입니다.

545의 경우 5+4+5 = 14가 최적의 돌의 경우의 수입니다.

만약 반올림을 해버리는 경우 5+5+5 = 15가 되기 때문에 더 많은 돌을 사용하게 됩니다.

555의 경우가 제일 헷갈려서 시간을 오래쓰게 되었습니다.

555의 경우,

560 -> +5  : 5번(+1)
600 -> +40 : 4번(+10)
1000 -> +400 : 4번(+100)
0 -> -1000 : 1번(-1000)

if(count==5&&storey%100<50){
	answer+=count;
}

해당 if문을 통해 10의 자리 수가5보다 작은 경우에는 반올림을 해주지 않고 그대로 - 를 감행하고, 반대의 경우에는 반올림을 진행하여 이득을 보는 형태로 코드를 사용하였습니다.

4. 테스트 케이스

999 -> 1+1 = 2

55 -> 5+5 = 10

75 -> 5+2+1 = 8

155 -> 5+4+2 = 11

545 -> 5+4+5 = 14

555 -> 5+4+4+1 = 14

1. 문제

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

2. 코드

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

using namespace std;

vector<string> nums;
string aeiou[5]={"A","E","I","O","U"};

void repeatPermutation(string s, int maxLength)
{
    if(maxLength==s.size()) //문자열의 크기 == 채울 문자열 크기
    {
        nums.push_back(s);
        return; //재귀함수 종료
    }
    
    for(int i=0;i<5;i++){
        repeatPermutation(s+aeiou[i],maxLength); //재귀함수 호출
    }
}

int solution(string word) {
    int answer = 0;
    
    for(int i=1;i<=5;i++){
        repeatPermutation("",i);
    }
    
    sort(nums.begin(), nums.end());  

    for(int i=0;i<nums.size();i++){
        if(word==nums[i]){
            answer=i;
            break;
        }
    }
       
    return answer+1;
}

3. 해설

vector<string> nums;
string aeiou[5]={"A","E","I","O","U"};

void repeatPermutation(string s, int maxLength)
{
    if(maxLength==s.size()) //문자열의 크기 == 채울 문자열 크기
    {
        nums.push_back(s);
        return; //재귀함수 종료
    }
    
    for(int i=0;i<5;i++){
        repeatPermutation(s+aeiou[i],maxLength); //재귀함수 호출
    }
}

int solution(string word) {
    int answer = 0;
    
    for(int i=1;i<=5;i++){
        repeatPermutation("",i);
    }

재귀 함수를 통해서 모든 경우의 수를 저장합니다.

경우의 수는 1자리일 때, 2자리일 때, 3자리일 때, 4자리일 때, 5자리일 때 모든 경우의 수를 구해야합니다.

따라서 1자리의 경우

for(int i=0;i<5;i++){
        repeatPermutation(s+aeiou[i],maxLength); //재귀함수 호출
}

이 부분이 aeiou[0] ~aeiou[4] 까지의 값이 한번씩 호출 되면서 끝납니다.

2자리의 경우 위의 for문이 aeiou[0]+aeiou[0]~aeiou[4] 에서부터 aeiou[4]+aeiou[0]~aeiou[4] 까지 계산함으로 총 25가지의 문자열이 저장됩니다.

이와 같은 방법으로 5자리의 경우까지 재귀함수를 통해 저장합니다. 

sort(nums.begin(), nums.end());  

    for(int i=0;i<nums.size();i++){
        if(word==nums[i]){
            answer=i;
            break;
        }
    }
       
    return answer+1;
}

그 후, 사전적 배열로 나열해줘야합니다.

기존에 저장된 배열은 A,E,I,O,U,AA,AE,AI,AO,AU.... 등의 순서로 구성되어 있습니다.(함수 호출 순서에 따라 달라질 수 있으나 (1자리수...2자리수...3자리수.... 로 저장)

기본적으로 sort 함수는 string 변수에서 사전적 순서로 정렬해주기 때문에 별도의 판별 함수를 넣지 않아도 됩니다.

그 후 for문을 통해 받은 word 값과 nums[i]의 값이 같다면 해당 번호를 뽑아냅니다.

벡터는 0번부터 시작하기에 +1을 해주면 몇번째 수인지를 도출할 수 있습니다.

※ for문을 쓰지 않고 find() 함수를 통해서 한줄로 해결할 수도 있습니다.

1. 문제

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

유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

2. 코드

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

using namespace std;

//수열 next_permutation을 활용하여서 풀이
//경우의 수를 다 계산한 다음 차례로 검증함
int solution(int k, vector<vector<int>> dungeons) {
    int answer = 0;
    
    vector<int> v;
    // 0부터 던전 사이즈까지 벡터에 저장
	for(int i=0; i<dungeons.size(); i++){
		v.push_back(i);
	}
    
    do{
        int pirodo=k;
        int count=0;
		for(int i=0; i<v.size(); i++){
            if(pirodo>=dungeons[v[i]][0]){
                //피로도 차감 및 던전 갯수 올리기
                count++;
                pirodo-=dungeons[v[i]][1];
            }
		}
        answer=max(answer,count);
	}while(next_permutation(v.begin(),v.end()));
    
    return answer;
}

3. 해설

//수열 next_permutation을 활용하여서 풀이
//경우의 수를 다 계산한 다음 차례로 검증함
int solution(int k, vector<vector<int>> dungeons) {
    int answer = 0;
    
    vector<int> v;
    // 0부터 던전 사이즈까지 벡터에 저장
	for(int i=0; i<dungeons.size(); i++){
		v.push_back(i);
	}

경우의 수가 많지 않기에 완전 탐색을 통해 풀수 있는 문제이다.

정해진 배열에서 순서를 바꾸는 경우의 수를 구할 때는 수열을 사용해서 만들어준다.

먼저 0~ 던전의 갯수 까지의 배열을 만들어준다.

만약 던전의 갯수가 3이라면 [0,1,2] 가 만들어진다.

  do{
	int pirodo=k;
	int count=0;
	for(int i=0; i<v.size(); i++){
        	if(pirodo>=dungeons[v[i]][0]){
                //피로도 차감 및 던전 갯수 올리기
                count++;
                pirodo-=dungeons[v[i]][1];
            }
	}
    	answer=max(answer,count);
}while(next_permutation(v.begin(),v.end()));

만들어진 배열을 가지고 next_permutation() 함수를 통해서 수열의 경우의 수를 출력한다.

do while문을 통해 수열의 경우의 수를 받아올 때 피로도와 던전이 필요한 최소 피로도를 넘긴다면 던전을 클리어하도록 설계한다.

만약 최소 피로도를 넘기지 못하면 계산하지 않고 넘어간다.

계산이 끝난 후 만약 Count가 기존의 answer보다 클 경우 answer에 count 값을 삽입한다.