작은시작

https://programmers.co.kr/learn/courses/30/lessons/43165

코드 설명

연산 (-,+)을 branch로 생각하여 DFS를 구성하였다.

처음 main문에서 넘겨주는 값을 number[level]로 했다가 바닥조건에서 이를 고려안해서 실수했다....

프로그래머스 환경에서 dfs 디버깅은 좀 쉽지 않은것 같다...

코드

#include <string>
#include <vector>

using namespace std;
int arr[2]={-1,1};
int answer=0;
void dfs(int level,int now,vector<int>&numbers,int target){
    if(level==numbers.size()){
        if(now==target) answer++;
        return;
    }
    for(int i=0;i<2;i++){
        int sum=numbers[level]*arr[i];
        now+=sum;
    
        dfs(level+1,now,numbers, target);
        now-=sum;
        
    }
    
}
int solution(vector<int> numbers, int target) {
    
    
    int n=numbers.size();
    dfs(0,0,numbers,target);
    
    return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/43238

코드 설명 

시간 이라는 개념을 이분탐색으로 찾아야 한다는게 포인트이다.

최소값은 1분 ~ 최대값은 times가 가진 최대 시간 * n(사람수) 이다.

그 후, mid시간 동안 몇명을 검사 할수 있는지 cnt를 통해 구한다. ( 구하는 법은 시간/times[i])

또한 최대값을 설정할때 long long 설정에 유의하자!

long long endd=n*(long long)times[k-1];

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    //입국심사 사람 1,000,000,000 => longlong 이분탐색 생각!
    sort(times.begin(),times.end());
    long long k=times.size();
    long long startt=1;
    long long endd=n*(long long)times[k-1];
    long long cnt=0;
    
    
    while(startt <= endd){
    long long midd=(startt+endd)/2;
        cnt=0;
     for(int i=0;i<k;i++){
        cnt += midd/times[i]; //시간당 심사인원한명이 심사할수 있는 인원수 합
    }
       
        if(cnt<n){  // 불가능
            startt = midd+1;    
        }
        else{ //가능 
            //최소시간 구하기
            answer=midd;
            endd=midd-1;
        }
        
    
    }
    
    
    
    return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/42747

코드 설명

문제의 이해가 푸는 시간보다 훨씬 더걸렸다....

문제 예시가 [3,0,6,1,5] 이다. 이를 인덱스와 비교해보면 (정렬 후)

0 6

1 5

2 3

3 1

4 0

순서로 인덱스가 더 커지지 않는 2까지 count하여 답은 3이다.

하나 더 생각해야 할점은 다음과 같이 구현하였을 때 [1,1,0,0,0] 케이스를 생각해보면 count와 원소값이 같다면 바로 리턴시켜주어야 한다.

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int solution(vector<int> citations) {
    int answer = 0;
    sort(citations.begin(),citations.end(),greater<int>());
    
    if(citations[0]==0) return answer;
    
    
    for(int i=0;i<citations.size();i++){
        if(i<=citations[i]){
            if(answer==citations[i]) break;
            answer++;
            
        }
        
  
    }
    
    
    return answer;
}

velog.io/@trevor522 에서 기록중