인덱스를 1씩 더해 옮기면서 현재 수를 더하거나 빼주는 방식으로 완전탐색해주기 function solution(numbers, target) { var answer = 0; function subset(cnt,sum){ if(cnt===numbers.length){ if(sum===target){ answer+=1; } return; } subset(cnt+1,sum+numbers[cnt]); subset(cnt+1,sum-numbers[cnt]); } subset(0,0); return answer; }
www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 맵을 1/4로 쪼개서 만드는 것은 한 번 해봐서 이번에는 익숙하게 했다. 안해봤다면 어려웠을 것이다. 1/4로 쪼갠 행과 열의 시작점과 길이(현재길이len의 반)을 재귀로 돌면된다. 시작점의 수와 해당 범위안에서 for문을 돌면서 하나라도 다른 원소가 있으면 다시 1/4로 쪼개서 재귀를 돌아준다. 재귀를 돌기 전에 (을 더하고 모든 원소가 갔을 때 시작점의 원소를 더해주고 재귀가 끝나면 )을 더해준..
www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 시간초과를 줄이기 위해서는 범위가 아닌 곳은 재귀로 추가 탐색하지 말아야된다. 만약 r보다 작거나 c보다 작은 곳은 ans값만 더해주고 건너뛴다. 더해주는 값은 (len/2)*(len/2)이다. len은 현재 탐색하는 사각형 한 변의 길이이다. import java.util.Scanner; public class Main { static int n,r,c; static int xpos[]= {0,1,0,..
www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 완전탐색 + 메모이제이션 기법을 사용 만약 같은 무게를 다시 재귀로 들어올 경우 기존보다 사용한 봉지의 수가 더 작을 경우만 vis[해당무게]를 업데이트하고 완전 탐색을 돌려준다. 만약 같은 무게인데 사용한 봉지의 수가 더 많은 경우는 더이상 검사할 필요가 없다. import java.util.Scanner; public class Main { static int n; static int ans=Integer.MAX_VA..
www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net from collections import deque from itertools import combinations import math n=int(input()) a=[list(map(int,input().split())) for _ in range(n)] p=[i for i in range(n)] allcase=combinations(p,n//2) ans=math.inf def check(start): global ans lin..