판교의 메타몽

백준 난이도별 문제 - 백트래킹의 최종문제. 그동안 풀었던 백트래킹 난이도별 문제에서 이것저것 개념을 영끌해서 풀어봤다. 실제로 각 문제들의 일부 포인트들을 차용하면 개념은 쉽게 포착할 수 있었다. 처음 만든 코드는 모든 예제에서 정답이 나왔으나, 시간초과가 나와버렸다. /* 1. 전체 수의 1/2과, 1/2~2/2까지에 해당되는 2개의 랜덤 조합을 만든다 2. 이 조합의 합산 값들의 최소값을 저장한다. */ #include #include #include #include #define MAX 20 using namespace std; int num = 0; int temp1, temp2 = 0; //임시 비교값 int minval = INT_MAX; int arr[MAX][MAX] = {0,}; boo..

문제 링크 : www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 전형적인 백 트래킹 문제. bool문으로 방문 여부를 확인하지 않고 오로지 if문을 통해 풀 수 있던 점이 편해서 좋았다. #include #include using namespace std; int n=0, mini = INT_MAX, maxi = INT_MIN, arr[12] = {0,}, pl=0, mi=0, mul=0, di=0; vo..

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3 www.acmicpc.net 스토쿠(9x9)에서 숫자를 집어 넣는데는 조건이 있다. 1. 가로 2. 세로 3. 3x3칸 이 세 가지에서 겹치는 숫자가 없어야 숫자를 넣..

#include #include #define MAX 16 using namespace std; int arr[MAX]; int N,ans = 0; bool check(int num){ for(int i=1; i N; dfs(0); cout

#include #define MAX 9 int arr[MAX]; bool check[MAX]; using namespace std; void BackTracking(int Count, int N, int M, int Start){ if(Count==M){ for(int i=0; i

#include #define MAX 9 int arr[MAX]; bool check[MAX]; using namespace std; void BackTracking(int Count, int N, int M){ if(Count==M){ for(int i=0; i

#include #include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); bool check1 = true; // 열의 홀 짝 (가로) bool check2 = true; // 행의 홀 짝 (세로) int T = 0; int num; cin >> num; while(T

#include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int num = 0; cin >> num; for(int i=0; i

#include #include using namespace std; int calculate(double a, double b){ double ans = 0; double i=0; for(; ; i++){ if(i*i>b-a) break;} i-=1; if(i*i==b-a) ans = i*2-1; else if(i*i T; int a[T]; for(int i=0; i> start >> end; if(end-start

#include #include #include using namespace std; bool check(paira, pairb){ return a.first> T; for(int i=0; i> age >> name; v.push_back(pair(age,name));} stable_sort(v.begin(),v.end(),check); for(int i=0; i