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)
www.acmicpc.net/problem/19639 19639번: 배틀로얄 첫 번째 줄에 X, Y, M (0 ≤ X, Y ≤ 100,000, 2 ≤ M ≤ 100,000)이 주어진다. M은 짝수다. 다음 X개의 줄에는 i번째 사람과 싸웠을 때 잃게 되는 체력이 주어진다. 이 수는 0 이상 M / 2 이하의 정수이다. www.acmicpc.net 아이디어: 어려웡.. 1. 포션은 체력이 m//2보다 같거나 작은 경우에만 섭취 2. 그러면 데미지의 합 > 초기 체력m+회복 합 인 경우를 걸러내면 불가능한 경우 걸러낼 수 있음. 3. 플레이어를 돌아가면서 데미지를 받고, 남은 체력이 m//2보다 같거나 작은 경우 체력이 m//2보다 같거나 크게 될때까지 포션 섭취. 만약 포션이 없으면 그대로 진행. 4. 플..
www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 아이디어: 어려워서 구글링함. 1. 일단 점수가 높은 순으로 정렬을 한다. 2. 과제 마감일에 가장 가깝게 배치한다. 그니까 최대한 늦게 과제를 제출한다. - 마감일에 이미 원소가 배치되어 있다면 인덱스 하나씩 감소시키면서 배치, 배치할 곳이 없다면 넘어가기 생각해볼 점: 로직을 직접 생각해야 되는데 구글링 해버렸당.. 과제 마감일에 가깝게 새로운 배열을 만들어서 원소를 넣는 방법이 있다는 걸 생각 못했음. 코드: 이차원 배열 정렬하는 방법 list.so..
www.acmicpc.net/problem/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주 www.acmicpc.net 아이디어: 처음에는 A를 만들어서 B와 같게 만들려고 했는데, B=[100]인 경우를 어떻게 해결해야 할 지 찾지 못했다. 그러던 중 구글링을 통해, B의 원소를 모두 0으로 만드는 방식으로 접근해야 한다는 걸 찾았다. 1. B를 오름차순으로 정렬한다. 2. B의 모든 원소가 2로 나누어떨어지도록 세팅한다. B의 원소가 2로 나누어떨어지지 않는 경우, B[i]-- ans++ 3. B의 모든 원소..
www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 아이디어: 값이 큰 동전을 최대한 많이 사용해야 사용하는 총 동전의 개수가 최소가 된다. 동전의 값은 오름차순으로 주어지므로, 주어진 동전 값을 순서대로 배열 arr에 넣고 인덱스 n-1부터 0까지 탐색하면서 k를 arr[i]로 나눈 몫을 더한다. 이때 k의 값은 k % arr[i]로 업데이트 하고 k % arr[i]가 0이되면 반복문을 탈출한다...
www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 아이디어: 돈을 인출하는 데 필요한 시간을 오름차순으로 정렬하면 된다. 코드: import sys n = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().split())) arr.sort() ans = 0 tmp = 0 for i in range(n): tmp += arr[i] ans += tmp print(ans)
www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 아이디어: 정확하게 N킬로그램을 만들 수 있는 경우, 5킬로그램으로 나누는 경우가 많을 수록 봉지의 개수가 적어진다. 따라서 N을 5킬로그램으로 나눌 수 있는 최대 수(N//5) ~ 최소 수(0) 까지 줄여가면서 N킬로그램이 정확하게 나누어 떨어지는 경우 봉지의 개수를 출력한다. 만약 5킬로그램 봉지가 0개인데도 N이 나누어지지 않는다면 -1을 출력한다. 코드: import sys n = int(sys.stdin.read..
www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 아이디어: 연산 = 3*3 크기의 부분 행렬에 있는 모든 원소를 뒤집는 것 -> 행렬 A의 원소를 3*3 크기의 부분 행렬의 왼쪽 위 꼭짓점으로 하여 돌면서 B와 같지 않을 경우 연산을 수행하고 연산의 개수를 ans 에 업데이트 한다. -> 모든 원소를 돌 필요는 없다. 3*3 크기의 부분 행렬의 개수는 정해져 있기 때문 -> 연산을 끝낸 행렬A와 행렬B가 같은지 비교 후 같지 않으면 -1을, 같으면 ans 출력 import..
