본문 바로가기

백준84

[9184] 신나는 함수 실행 내가 스스로 짜긴 했는데 완전 야매 느낌이라 다른 사람들의 풀이를 보고 고쳤다. ㅜㅜ 재귀 함수를 쓰면 시간 초과가 뜨겠지! 라는 생각에 사로잡혀 그냥 for문을 3번 돌렸다 결론적으로 맞았는데, 예제가 없었다면 틀렸을 것이다. 아주아주 부끄러운 풀이다. #include #include using namespace std; int a, b, c, aa, bb, cc; int w[101][101][101]; int change(int x) { // x가 음수 : 1~50 index에 저장 // x가 양수 : 51~100 index에 저장 if (x 0) { return x + 50; } } void f() { for (int i = 0; i.. 2022. 9. 23.
[14889] 스타트와 링크 처음에 문제를 잘 못 이해해서 삽질했다. 4명만 뽑으면 되는줄 ^^;; 문제를 잘 읽자. N/2명으로 나눠서 2팀을 만들고, 각각의 경우의 수를 따져야 한다. ex) 4명이 경기한다고 치자. 사람들 이름이 1, 2, 3, 4라고 치면 1 2 / 3 4 : | (S12+S21) - (S34+S43) | 1 3 / 2 4 : | (S13+S31) - (S24+S42) | 1 4 / 2 3 : | (S14+S41) - (S23+S32) | 총 3가지로 팀 구성이 될 수 있다. ex) 6명이 경기한다고 치자. 사람들 이름이 1, 2, 3, 4, 5, 6이라고 치면 1 2 3 / 4 5 6 : | (S12+S21+S13+S31+S23+S32) - (S45+S54+S46+S64+S56+S65) | 1 2 4 / 3.. 2022. 9. 21.
[2580] 스도쿠 0으로 채워진 곳을 내가 채워야 한다. 일단 스도쿠 성립의 조건은 총 3가지이다. 1. 가로에 똑같은 수가 없어야 함 2. 세로에 똑같은 수가 없어야 함 3. 해당하는 정사각형 3*3배열 안에 똑같은 수가 없어야 함 그래서 적합한지 따져주는 함수 is_Correct 함수를 만들었다. 1, 2번 조건은 다음과 같이 구현할 수 있다. // 1, 2 for (int i = 1; i 2022. 9. 16.
[9663] N-Queen 코딩 학원에 다녔을 때 풀었던 풀이를 보는데.. 당최 이해가 되지 않아서 다시 풀었다 #include using namespace std; int N, cnt, col[16], inc[32], dec[32]; void solve(int r) { if (r > N) { cnt++; return; } for (int i = 1; i > N; solve(1); printf("%d", cnt); } 저 inc와 dec 배열이 대각선을 따져주는 것 같긴 한데,, 시간을 두고 이해를 해봐야겠다ㅠㅠ 아무튼 다시 처음부터 다시 풀었다 이틀을 고민했다 일단 Queen을 놓는 조건은 상하좌우, 대각선에 거리 제한 없이 Queen이 위치해있으면 안된다 그럼 조건 2가지를 코드로 직접 작성해야지 일단 같은 행에 Queen을 .. 2022. 9. 8.
[15652] N과 M (4) 이번 조건은 특이하다 같은 수를 여러 번 골라도 되고, 고른 수열이 비내림차순이어야 한다 비내림차순 : 각각의 원소가 바로 앞에 있는 원소보다 크거나 같아야 함 ex) 1 2 2. 2 2 3, 4 5 6 https://kmyobin.tistory.com/58?category=1084833 [15649] N과 M (1) 백트래킹 문제이다 오랜만에 다시 공부하니까 머리 터질 것 같다 dfs 방식으로 문제를 풀 것이다 1. 중복이 되지 않으면서 2. 순열(순서를 따짐) 이어야 한다 그래프를 그려보면 일단 중복인 값들 kmyobin.tistory.com 전에 만들어놓았던 백트래킹 과정이 정말 도움이 많이 되었다 저기서 (2,1)이 출력되지 않으려면 어떻게 해야될까..! 바로 전에 담았던 숫자를 기억하는 변수 하.. 2022. 9. 6.
[15651] N과 M (3) https://kmyobin.tistory.com/58?category=1084833 [15649] N과 M (1) 백트래킹 문제이다 오랜만에 다시 공부하니까 머리 터질 것 같다 dfs 방식으로 문제를 풀 것이다 1. 중복이 되지 않으면서 2. 순열(순서를 따짐) 이어야 한다 그래프를 그려보면 일단 중복인 값들 kmyobin.tistory.com 백준 15649번과 다른 점은 같은 수를 여러 번 골라도 된다는 것. 전에는 같은 수를 다시 반복해서는 안됐기 때문에 visited 배열을 만들어줘서 해당 숫자를 사용했었는지 따져보았는데, 이제 그럴 필요가 없다 그러므로 기존에 풀었던 15649번 코드에서 visited와 관련된 코드를 빼면 완성된다 그렇게 완성된 코드는 아래와 같다 #include using .. 2022. 9. 6.
[15650] N과 M (2) https://kmyobin.tistory.com/58 [15649] N과 M (1) 백트래킹 문제이다 오랜만에 다시 공부하니까 머리 터질 것 같다 dfs 방식으로 문제를 풀 것이다 1. 중복이 되지 않으면서 2. 순열(순서를 따짐) 이어야 한다 그래프를 그려보면 일단 중복인 값들 kmyobin.tistory.com 이 문제와 유사하다 그래서 처음에 풀 때는 기존에 풀었던 15649 코드에 덧붙여서 코드를 완성했다 일단 15649에서 했던 것과 동일하게 A배열을 구한 후, 이 것이 오름차순 배열인지 따져본 다음 오름차순 배열일 때만 출력하게 만들었다 #include #include using namespace std; int N, M; int A[8]; int tmp[8]; bool visited[9];.. 2022. 9. 4.
[15649] N과 M (1) 백트래킹 문제이다 오랜만에 다시 공부하니까 머리 터질 것 같다 dfs 방식으로 문제를 풀 것이다 1. 중복이 되지 않으면서 2. 순열(순서를 따짐) 이어야 한다 그래프를 그려보면 일단 중복인 값들은 들어가면 안되겠죠? 그렇게 탐색한 과정이 위와 같다 그렇다면 중복인 값을 걸러주기 위해 visited 배열을 만든다 말로 설명하기 어려우니 직접 돌아가는 과정을 적어보았다 N=4, M=2인 경우이다 마지막에 visited[i]=false는 print 후 원상복구 시키는 역할을 한다 visited[i]=true는 dfs로 더 깊숙히 들어갈 때 중복되는 숫자를 방지하기 위함이다 그렇게 완성된 코드는 아래와 같다(틀을 외우도록 하자) #include using namespace std; int N, M; int A.. 2022. 9. 4.
[2004] 조합 0의 개수 조합은 알다시피 nCr=(n!)/[{(n-m)!}(m!)] 으로 구할 수 있다 팩토리얼 0의 개수를 구하는 방법을 알았으니, f(n) - f(n-m) - f(m)을 하면 조합 0의 개수가 나올 줄 알았다 0의 개수는 결국 10의 개수인건데, 분모로부터 분자에 있는 10의 개수를 빼야 최종 10의 개수가 나오기 때문이다 그래서 이 문제를 참고했는데 https://kmyobin.tistory.com/56 [1676] 팩토리얼 0의 개수 소인수분해의 특징을 찾으라는데, 나는 규칙을 찾아서 풀었다 5의 배수일 때 0의 개수가 늘어나는데, 만약 25의 배수면 하나 더 증가, 125의 배수면 또 하나 증가가 되는 성질을 발견하였다 그래서 kmyobin.tistory.com 이거대로 했더니 틀렸다 5의 x제곱의 개수.. 2022. 9. 3.
[1676] 팩토리얼 0의 개수 소인수분해의 특징을 찾으라는데, 나는 규칙을 찾아서 풀었다 5의 배수일 때 0의 개수가 늘어나는데, 만약 25의 배수면 하나 더 증가, 125의 배수면 또 하나 증가가 되는 성질을 발견하였다 그래서 미리 크기 501의 배열을 만든 후 그 안에 0의 개수를 for문을 이용하여 할당해주었다 다시 보니 5의 x제곱일 때 k가 x씩 늘어나는 것 같다 하지만 크기가 500까지였으므로 굳이 정리하여 적진 않았다 그렇게 완성된 코드는 아래와 같다 #include using namespace std; int A[501]; int N; void f() { int k = 0; for (int i = 0; i > N; printf("%d",A[N]); } 문제를 풀고 난 후 다른 사람들의 풀이를 보았다 0의 개수를 구한다는.. 2022. 9. 3.

티스토리툴바