meenyweeny iOS

2309번 일곱 난쟁이 그냥 9개의 숫자 중, 합이 100이 되는 7개의 숫자를 찾으라는 것이다. (스페셜 저지는 문제의 정답 조건을 만족하는 것들 중 아무거나 출력하는 문제임) 그냥 단순하게, 난쟁이가 겹치지 않게 (한 사람 두 번 세지 않도록) 정답 조건(7명이며, 키의 합이 100일 것)을 확인하는 재귀함수 돌렸다. for문 7개 쓸 순 없으니까.. ^^ (for문 7개 써도 된다,, 당연히 결과는 같음!!) C++ #include #include #include using namespace std; int height[9]; vector answer; void solve(int next_index, int count, int sum, vector list) { if(count==7 && sum==..

2798번 블랙잭 문제 다 읽을 필요도 없다. 카드를 고르는 것이기 때문에, 카드 세 장을 골랐을 때 세 장의 카드는 모두 달라야한다는 생각 하나만 가지고 브루트포스하게 문제를 풀면 된다. (숫자가 겹치면 안된다는 것이 아님) 간단히 3중 for문으로 해결 가능하다. 아래 코드에서처럼, O(n^3) 의 시간복잡도 내에 문제 해결 가능한데 주어진 n은 많아야 100개 최악의 경우에도 주어진 1초를 넘지 않는다. C++ #include #include using namespace std; int n,m,sum,ans; int arr[100]; int main() { cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false); cin>>n>>m; for(..

브루트포스 문제 연습해보려고 골랐다 브루트포스에 제일 자신없기 때문이다 . . . 그니까 짝수인 N개의 입력이 들어오면 N/2개의 조합끼리의 합이랑, 나머지의 합을 구하면 될것같다고 생각했다 그리고 문제 시간 제한이 2초나 되는데, N의 입력 제한이 20이길래, 조합의 중복까지 모두 구해도 될 것 같다고 생각해서 그냥 따로 중복에 관한 처리를 해주지 않고, 그냥 bool 배열 하나 만들어서 일반적으로 구했다 nPr을 구했나봐.. 그랬더니 당연히 시간초과가 생겼다 겹치지 않는 조합으로 바꿔주니까 바로 해결되었다 0부터 n까지 차례대로 방문하며 돌기 때문에, 조합에서 다음 수를 구할땐 단순히 전의 수부터 끝 수까지 보면 된다 다음 수는 또 그 전 수부터 끝 수까지 중에 하나 이런 식으로 고쳤다 또, 방문을 ..

브루트포스 문제를 연습해보려고 카테고리에서 고른 문제 문제에서 선택된 숫자는 모두 달라야 한다고 해서 숫자의 방문 여부를 표시해주는 bool 배열을 사용하며 재귀로 구현해야겠다고 생각했다 근데 난 재귀에 자신이 없다 하하 . . . 또, 출력 정수는 문자열이어야 한다고 해서 애초에 답 저장을 vector에 string으로 넣었다 (to_string 함수를 써서) 그리고 0부터 9까지 방문 여부를 확인하며 하나씩 탐색하기 때문에, 이미 ascending order로 정렬되어있을 것이다 조건을 만족하는 수면 string에 to_string으로 하나씩 붙여주고, 재귀함수의 파라미터로 답을 저장한 문자열, 지금 몇번째 재귀(?)인지, 바로 전 숫자가 뭔지(비교해야하니까) 넘겨줬다 그런데 정답이 아니었을때 처리나..