박기완 코딩교육/코딩테스트 대비

프로그래머스 타겟 넘버 문제

hackee 2020. 10. 18. 02:34

안녕하세요! 오늘은  프로그래머스의  '타겟 넘버'를 풀어보았습니다.

 

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

 

코딩테스트 연습 - 타겟 넘버

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+

programmers.co.kr

 

단순히  각 숫자를 더하냐 빼냐를 최대 20번 반복하는 형태여서   2의 20승.  최대 백만번 호출로 정답을 찾을 수 있었습니다.

전체탐색 방법으로  반복문을 돌리든, 재귀함수를 돌리든  편한걸 택하면 되는데,   

전 재귀함수가 좀더 직관적인거같아   재귀로 구현했습니다.

 

#include <string>
#include <vector>

using namespace std;


void findCase(int step, int sum, int target, vector<int> &numbers, int &answer){
    if(step == numbers.size()){
        if(sum == target){
            answer++;
        }
        return;
    }
    
    //해당 숫자를 더하거나 빼거나 
    findCase(step+1, sum + numbers[step], target, numbers,answer);
    findCase(step+1, sum - numbers[step], target, numbers,answer);
    
}

int solution(vector<int> numbers, int target) {
    int answer = 0;
    
    //경우의 수 다 찾기
    findCase(0, 0, target,numbers, answer);
    return answer;
}

 

 

<박기완의 c언어 코딩교육 시리즈 >

 

게임개발을 희망하는 초등학생, 중학생, 고등학생들을 위한 c언어 책

이 글을 보고있다는건 게임개발에 관심있다는 거겠죠? 그렇다면 정말 잘보셨습니다. 읽기 쉽고,  단기간 내에 자기꺼화 할 수 있게 최대한 핵심만 담았습니다. 게임을 어떻게 만드는지 궁금해

blog.codingteacher.kr

 

초등, 중등, 고등  1:1 원격 c언어 교육문의

010 - 4537 - 7998

 

현재 대치동 학원에서 코딩강사로 활동중에 있습니다

영재고, 과학고 내신 /

초등, 중등, 고등 입문반, 초급, 중급, 정올반 /

앱, 게임 제작반  문의주세요!