박기완 코딩교육/코딩테스트 대비
프로그래머스 타겟 넘버 문제
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언어 책
이 글을 보고있다는건 게임개발에 관심있다는 거겠죠? 그렇다면 정말 잘보셨습니다. 읽기 쉽고, 단기간 내에 자기꺼화 할 수 있게 최대한 핵심만 담았습니다. 게임을 어떻게 만드는지 궁금해
blog.codingteacher.kr
초등, 중등, 고등 1:1 원격 c언어 교육문의
010 - 4537 - 7998
현재 대치동 학원에서 코딩강사로 활동중에 있습니다
영재고, 과학고 내신 /
초등, 중등, 고등 입문반, 초급, 중급, 정올반 /
앱, 게임 제작반 문의주세요!