https://school.programmers.co.kr/learn/courses/30/lessons/388352
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
문제에 대놓고 조합을 쓰라고 나왔다.
다만, 시간초과가 날까봐 처음에 망설여졌는데 30C5이면, 1억번을 넘지 않았다.
또한 30C5으로 고르고 나서 ans로 들어온 배열들과 비교를 해야되는데, 30C5 * 10 * log(10)을 해도
142,506 * 10 * log(10)
이므로 1억번에 미치지 못한다.
풀이
- for문으로 반복문 다 돌렸다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int n, vector<vector<int>> q, vector<int> ans) {
int answer = 0;
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
for(int k=j+1;k<=n;k++) {
for(int y=k+1;y<=n;y++) {
for(int z=y+1;z<=n;z++) {
int size = ans.size();
vector<int> cnt(size);
for(int p=0;p<q.size();p++) {
for(int w=0;w<5;w++) {
if (q[p][w] == i) {
cnt[p]++;
} else if (q[p][w] == j) {
cnt[p]++;
} else if (q[p][w] == k) {
cnt[p]++;
} else if (q[p][w] == y) {
cnt[p]++;
} else if (q[p][w] == z) {
cnt[p]++;
}
}
}
bool flag = true;
for(int p=0;p<q.size();p++) {
if (ans[p] != cnt[p]) {
flag = false;
break;
}
}
if (flag) {
answer++;
}
}
}
}
}
}
return answer;
}
5개까지라 for문을 돌려서 해도 충분했다.. [내가 읽기에]
물론 재귀를 이용해서도 풀 수 있다.
하지만 프로그래머스 환경에서는 전역변수를 쓰고, 하기가 조금 까다로워 for문으로 접근했다.
#include <string>
#include <vector>
using namespace std;
void go(int start, int n, vector<int>& selected,
vector<vector<int>>& q, vector<int>& ans, int& answer) {
// 5개를 다 선택했으면 검사
if (selected.size() == 5) {
bool valid = true;
for (int p = 0; p < q.size(); p++) {
int cnt = 0;
for (int w = 0; w < 5; w++) {
for (int s : selected) {
if (q[p][w] == s) {
cnt++;
break;
}
}
}
if (cnt != ans[p]) {
valid = false;
break;
}
}
if (valid) answer++;
return;
}
// start부터 n까지 하나씩 선택해보기
for (int i = start; i <= n; i++) {
selected.push_back(i);
go(i + 1, n, selected, q, ans, answer);
selected.pop_back(); // 백트래킹
}
}
int solution(int n, vector<vector<int>> q, vector<int> ans) {
int answer = 0;
vector<int> selected;
go(1, n, selected, q, ans, answer);
return answer;
}반응형
'PS' 카테고리의 다른 글
| [프로그래머스 Lv.2] 도넛과 막대 그래프 (0) | 2025.12.12 |
|---|---|
| [프로그래머스 Lv.2] 퍼즐 게임 챌린지 (0) | 2025.12.11 |
| [BOJ 1027] 고층 건물 (1) | 2025.12.09 |
| [프로그래머스 Lv.2] 서버 증설 횟수 (0) | 2025.12.09 |
| [프로그래머스 Lv.2] 완전범죄 (0) | 2025.12.08 |