www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 아이디어: 사전 순으로 증가하는 순서로 출력해야 하므로 입력으로 주어진 N개의 자연수 정렬. 중복되는 수열을 체크할 방법이 관건. -> 일단 각 숫자가 사용되었는지 여부를 확인하는 isUsed = [N] -> 중복되는 수열인지 체크는 바로 이전에 출력한 수열과 동일한지 체크하면 되지 않을까?(X) -> 테스트 케이스 2번째의 경우처럼 똑같은 원소가 여러 개 있을 경우 중복 체크가 안됨 -> 바로 이전에 선택한..
알고리즘💻/Bruteforce&Backtracking
www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 아이디어: 인덱스 i*j 각 열에 퀸이 하나씩 있어야 한다. for i in (0~N) 1. 같은 행 -> j 2. 오른쪽 위 대각선 -> i+j 3. 오른쪽 아래 대각선 -> i-j+N-1 (인덱스가 음수가 나오면 안되니까) 코드: 파이썬 함수 안에서 변수의 값을 바꾼 후 나와서 출력시킬 때.. 전역변수를 설정해야 한다. global import sys n = int(sys.stdin.readline()) check1 = [..
www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 아이디어: 역시 재귀함수를 이용한다. 오름차순으로 출력하므로 중복을 따로 검사하지 않아도 중복이 보장된다. 코드: import sys n, m = map(int, sys.stdin.readline().split()) ans = [0]*m def solve(level, start): if (level==m): for i in ans: print(i, end=" ") print() return for i in r..
www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 아이디어: 재귀함수 이용. solve(level) -> level == m 이되면 출력하고 return for (1, n+1) 까지 중복 여부를 검사(isused[] 배열을 이용)하고 중복되지 않는 경우 정답 배열에 추가 재귀함수 이용법 숙지 코드: import sys n, m = map(int, sys.stdin.readline().split()) isUsed = [False]*n ans = [0]*m de..
www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 아이디어: N과 M은 8보다 크거나 작고, 50보다 작거나 같은 자연수이므로 8*8의 가능한 모든 경우를 찾고, 각 경우에 칠해야 하는 정사각형의 최소 개수를 모두 구해도 주어진 ㅅ ㅣ간 내에 해결 가능하다.(브루트포스) 8*8 가능한 모든 경우: for (0~N-8)까지 탐색 칠해야 하는 정사각형의 최소 개수: 칠할 수 있는 경우는 W가 i+j=짝수 이고 B는 i+j 홀수인 경우와, W는 홀수, B는 ..
www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 아이디어: N0): sum += temp %10 temp //= 10 if (sum==n): ans = i break print(ans)
