알고리즘/프로그래머스28 [ 프로그래머스 / Map ] 위장 1. 문제 코딩테스트 연습 - 위장 programmers.co.kr 2. 소스코드 - 옷의 카테고리별로 map을 만든 뒤, 카테고리별 갯수를 저장 - 가능한 경우의 수는, 해당 카테고리별 옷의 개수 를 전부 곱해주고 - 1이다. - -1을 하는 이유는 아무것도 안입는 경우의 수이기 때문. 소스코드 #include #include #include #include using namespace std; int solution(vector clothes) { unordered_map map; int answer = 1; vector ctg; for(auto cur : clothes){ if(map[cur[1]] == 0) ctg.push_back(cur[1]); map[cur[1]]++; } for(string.. 2020. 6. 30. [ 프로그래머스 / DFS ] 타겟 넘버 1. 문제 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 2. 소스코드 - 매우 간단한 DFS문제 소스코드 #include #include using namespace std; int ans, t; vectorcopy_numbers; void dfs(int sum, int depth){ if(depth >= copy_numbers.size()) { if(sum == t) ans++; return; } dfs(sum + copy_numbers[depth] .. 2020. 6. 30. [ 프로그래머스 / 투포인트 ] 숫자의 표현 1. 문제 코딩테스트 연습 - 숫자의 표현 Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 programmers.co.kr 2. 소스코드 소스코드 #include #include using namespace std; int solution(int n) { int answer = 0, start = 1, end = 1, sum = start; while (!(start > n or end > n)) { if (sum == n) { answer++; sum -= start++; } else if (sum < n) { sum += ++end; } else i.. 2020. 6. 30. [ 프로그래머스 / DP ] 땅따먹기 1. 문제 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟�� programmers.co.kr 2. 소스코드 - 이 문제는 그리디로 풀면, 당연히 최적해를 보장하지 않는다. - 완전 탐색을 하자니, 열은 4개지만, 행의 개수가 10만이다. 완전 탐색도 불가. - 그래서 DP 구나 싶었다. - [x][y]까지의 최대값은 [x][y] + [x-1]행에서의 최대값 이다. (단, 열은 달라야한다) 소스코드 #include #include using namespace std; int dp[100001][4]; int solutio.. 2020. 6. 30. 이전 1 ··· 3 4 5 6 7 다음