작심 24/7

14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 순열 문제의 변형이다. 연산자 배열을 만들어 나열시켜주고 순열 알고리즘 처럼 check 배열을 만들어 갔다 온 곳은 체크 해준다. 재귀를 이용해서 끝까지 계산 해주고 완료되면 최댓값 최솟값 비교를 해준다. 재귀가 끝나고 돌아오면 값을 이전 값으로 다시 만들어주며 반복한다. #include #include using namespace std; int Max = -1111111111, M..

2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 백트래킹으로 푸는 문제이다. 1. 같은 행에 숫자 N이 없을 때 2. 같은 열에 숫자 N이 없을 때 3. 같은 3*3 칸에 숫자 N이 없을 때 이 세 조건을 충족시키면 다음 빈칸을 채우러 가고 만족시키지 못한다면 N+1을 하여 다음 숫자를 넣어본다. N을 9까지 증가시켰는데 빈칸을 채우는데 실패하면 이전 빈칸의 숫자가 잘못된 것이므로 돌아간다. 모든 빈칸이 채워지는 경우엔 finish에 표시한 후 모두 빠져나와 출력시키면 끝 #include #include us..

9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹의 대표적인 문제이다. 이차원 배열을 만들 필요 없이 일차원 배열로 인덱스는 행, 값은 열을 넣어주어 풀 수 있다. 퀸이 배치될 수 있는 조건은 1. 같은 행에 있지 않을 때 2. 같은 열에 있지 않을 때 3. 같은 대각선 상에 있지 않을 때 이다. 1번의 경우는 queen이라는 일차원 배열을 만듦으로써 행이 겹칠 수가 없게 된다. 2번과 3번의 경우는 인덱스 0부터 현재 행 전까지 돌아가는 for문을 끝까지 돌면서 현재 위치가 queen을 놓을 수 있는 조건인 경우 다..

15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N개 중에 중복 포함, 순서 상관없이 M개를 뽑는 중복 조합 문제이다. 앞의 값보다 크거나 같은 값일 경우에만 벡터에 넣어주고 카운트가 M일 때 출력해주면 된다. #include #include using namespace std; vector v; int cnt = 0; void multiCombination(int N, int M, int start) { if (cnt == M) { for (int i = 0; i < v.size(); i..

15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N개 중에 중복 포함, 순서를 고려하여 M개를 뽑는 중복 순열 문제이다. 순열과 다른 점은 중복을 체크해줄 필요 없기 때문에 check배열만 없애면 된다. 자바는 Scanner + print 써서 그냥 제출하니까 시간 초과 나길래 Scanner 대신 BufferedReader를 썼더니 또 시간 초과됐다 (자바 싫어) 찾아보니 print가 시간이 꽤 오래 걸린다 하더라 그래서 출력 부분을 StringBuilder로 넣어준 뒤 마지막에 한 번만 출력시켰더니 통과 <..

15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N개 중에 중복 미 포함, 순서 상관없이 M개를 뽑는 조합 문제이다. 이번엔 check 배열이 필요 없다. 앞의 값보다 큰 값일 경우에만 벡터에 넣어주고 카운트가 M일 때 출력해주면 된다. #include #include using namespace std; vector v; int cnt = 0; void combination(int N, int M, int start) { if (cnt == M) { for (int i = 0; i < v..

15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N개 중에 중복 미 포함, 순서를 고려하여 M개를 뽑는 순열 문제이다. 바로바로 출력을 할 수 없기 때문에 벡터를 만들어 값을 저장하고 빼주면서 출력해준다. 대충 이런 식으로 돌아가는 구성이다. #include #include using namespace std; vector v; int check[10] = { 0 }; int cnt = 0; void permutation(int N, int M) { if (cnt == M) { for (i..

10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 � www.acmicpc.net vector의 pair기능과 compare함수를 이용하면 쉽게 풀 수 있는 문제이다. compare 없이 그냥 sort를 해주면 vector의 first를 기준으로 정렬되기 때문에 second.first(나이)가 같으면 second.second(인덱스 값)이 증가하는 순으로 정렬시키도록 compare함수를 작성해주면 끝 #include #include #include #include using namespace std; vector v; bool c..