투투

문제 NxM크기의 체스보드가 있다. 체스보드는 검은색과 흰색이 번갈아가면서 칠해져 있어야한다. 8X8크기로 체스보드를 잘랐을 때 다시 칠해야 하는 칸이 최소일 때의 개수를 구하라. 입력 첫째 줄에 N과 M이 주어지며 N과 M은 8이상 50이하이다. 둘재 줄부터 체스판의 정보가 입력되며 W는 흰색, B는 검정색이다. 출력 다시 칠해야 하는 칸의 최솟값을 출력한다. 8x8 크기의 체스판이 제대로 칠해져 있는 경우는 두 가지이다. 검, 흰이 번갈아가면서 칠해질 때 (0, 0)의 칸이 검정색 또는 흰색으로 시작하는 경우이다. 따라서 입력받은 체스판을 8x8크기로 잘라서 두 개의 알맞는 체스판과 비교를 한다. 체스판을 어떻게 자를지 생각을 많이했다. 결론적으로 시작점의 위치만 알면 비교가 가능하다는 것을 알게되었..

문제 N개의 정수로 이루어진 수열이 있을 때, 부분수열 중에서 그 수열의 원소를 모두 더한 값이 S가 되는 경우의 수를 구하라. 입력 첫째 줄에 정수의 개수 N(1이상 20이하)과 S(절댓값 백만)를 입력 둘째 줄에 N개의 정수를 입력하며 각 정수는 절댓값 십만을 넘지 않는다. 출력 합이 S가 되는 부분수열의 개수를 출력 모든 부분수열의 합을 탐색해야 한다. 따라서 모든 부분수열을 생성할 수 있는 방법을 생각해봐야 한다. 나는 1부터 N개를 포함한 부분수열이 존재하기 때문에 부분수열의 개수에 따라 부분수열을 생성하도록 하였다. 이후 해당 개수를 갖는 부분수열의 합을 백트래킹으로 구하여 S와 맞는지 검사하였다. #include "pch.h" #include #include #include using nam..

문제 짝수인 N명의 사람들이 팀을 두 개로 나누어 축구를 한다. 이때 i와 j가 한 팀일 때의 능력치를 나타내는 표가 있을 때 양 팀의 능력치 합에 대한 차이를 최소로 했을 때의 값을 출력하라 입력 첫째 줄에 N(짝수, 4이상 20이하) 둘째 줄부터 N개의 줄에 능력치를 입력한다. 출력 능력치 차이의 최솟값을 출력 두 팀으로 나누는 방법을 먼저 생각해봐야 한다. 사람들은 고유의 등번호를 갖고있으므로 각 번호에 팀 번호를 부착하여 팀을 나누도록 한다. team이라는 배열을 선언하여 각 번호에 해당하는 사람이 어느 팀인지 구분하도록 한다. 사람의 수만큼 for문을 돌아 백트래킹으로 팀을 나누고 팀을 다 나누었다면 각 팀의 능력치를 구하도록 한다. 능력치를 구하는 것은 어렵지 않다. 만약 해당 인덱스들이 1번..

문제 N개의 수로 이루어진 수열이 있을 때 N-1개의 연산자를 수와 수사이에 끼워넣어 연산을 진행한다. 이때 최솟값과 최댓값을 구하라. 단, 수는 이동할 수 없으면 식의 계산은 연산자 우선순위를 무시하고 앞에서부터 진행한다. 또한 나눗셈은 정수 나눗셈으로 몫만 취한다. 입력 첫째 줄에 수의 개수 N(2이상 11이하) 둘째 줄에는 N개의 수열을 입력 셋째 줄에는 합이 N-1인 4개의 정수가 주어지며 차례대로 덧셈, 뺄셈, 곱셈, 나눗셈의 개수를 의미한다. 출력 첫째 줄에 최댓값 둘째 줄에 최솟값 입력받은 수열은 고정이고 연산자의 개수 안에서 조합하여 최댓값, 최솟값을 출력해야한다. 따라서 두 가지를 고려해봐야 했다. 1. 연산자를 선택하는 조합 2. 조합된 연산자를 통해 수를 계산하기 연산자의 모든 경우의..

문제 연구의 크기가 NxM일 때 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 바이러스가 퍼지는 것을 막기위해 벽은 3개를 세울 수 있다. 3개의 벽을 세운 뒤에 바이러스가 퍼질 수 없는 곳을 안전영역이라 하는데 안전영역 크기의 최댓값을 구하라. 입력 첫째 줄에 지도의 크기인 N, M 입력 3이상 8이하 둘째 줄부터 지도의 모양을 입력하며 바이러스인 2의 개수는 2이상 10이하이다. 빈 칸의 개수는 3개 이상 출력 안전영역의 최댓값을 출력 문제에서 반드시 3개의 벽을 세워야한다고 했다. 여기서 다음 두 가지를 구현하면된다. 1. 벽을 세우는 로직 2. 벽을 세운 후에 바이러스를 퍼트리는 로직 먼저 벽을 세우는 로직을 어떻게 구현하면 좋을지 생각해보자. 맵에서 0은 빈 칸이고 벽을 세울 수 있는 ..

문제 K개의 수 중 6개의 수를 중복없이 선택할 수 있는 모든 경우의 수를 출력하라. 입력 K입력 후 K개의 수를 입력한다. 이때 0을 입력하면 종료된다. 출력 각 케이스에 대한 모든 경우의 수를 출력한다. c++ 1. 6개의 수를 선택하는 것은 Lotto함수에서 이루어진다. 2. 함수의 매개변수는 다음 인덱스와 지금까지 선택한 수를 넘겨준다. 3. 선택한 것이 6개라면 vector에 있는 수를 출력한다. 4. for문을 돌리고 vector에 수를 하나씩 대입하고 현재인덱스+1, 선택+1을 함수에 넘겨주고 4. 함수가 끝나고 돌아왔을 때 다시 원래의 상태가 되도록 vector에서 수 하나를 뺀다. 5. 위의 과정을 계속 반복하여 모든 경우의 수를 출력한다. #include "pch.h" #include ..

문제 A와 B로만 이루어진 글자가 있다. 단어 중에서 같은 글자끼리 글자위로 아치형 곡선을 그었을 때 아치형 곡선이 교차하지 않으면 좋은단어이다. N개의 단어 중 좋은 단어가 몇 개인지 출력하라. 입력 첫째 줄에 단어의 수 N이 주어진다. 다음 N개의 줄에 A와 B로만 이루어진 단어가 한 줄씩 입력된다. 출력 좋은 단어의 개수를 출력한다. C++ 같은 글자끼리 글자 위로 아치형 곡선을 그었을 때 교차가되지 않는 조건은 가운데를 기준으로 대칭일 때이다. 대칭을 판단하기 위해 스택을 활용한다. 1. N개의 단어를 입력받을 때마다 다음을 반복한다. 2. 글자를 입력받고 처음부터 탐색을 진행한다. 3. 현재 스택이 비어있으면 현재 글자를 push()한다. 3. 비어있지 않다면 스택의 top()과 비교하고 현재 ..

문제 재현이는 재민이를 도와서 돈을 관리 중이다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서 가장 최근에 재민이가 쓴 수를 지우도록한다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 구한다. 입력 첫 번째 줄에 정수 K 이후 K개의 줄에 정수가 1개씩 주어진다. 0일 때는 가장 최근의 수를 지우고 아닐 경우 해당 수를 쓴다 출력 최종적으로 적어 낸 수의 합을 출력한다. C++ 숫자를 입력하다가 0이 나오면 가장 최근에 입력한 수를 제거해야한다. 따라서 스택의 특성을 활용할 수 있다. 스택은 데이터를 넣고 빼는 입구가 한 개이다. 그래서 데이터를 넣다가 뺀다면 가장 최근에 넣었던 데이터가 제거된다. 다음은 스택을 이용한 풀이과정이다. 1. 입력된 K만큼 숫자를 입력하여 num에 저장한다. 2..

문제 사람의 덩치를 비교할 때 몸무게와 키를 이용한다. A와 B의 (몸무게, 키)가 각각 (x, y), (p, q)이고 x>p, y>q라면 A는 B보다 덩치가 크다고 할 수 있다. 하지만 xq라면 비교할 수 없다. 따라서 자신보다 몸무게와 키가 큰 사람의 수+1이 자신의 등수가 된다. N명의 사람에 대한 몸무게와 키가 주어질 때 등수를 순서대로 출력해보자 입력 첫 줄에는 전체 사람의 수 N이 주어진다. 그리고 이어지는 N개의 줄에는 각 사람의 몸무게와 키를 나타내는 양의 정수 x와 y가 하나의 공백을 두고 각각 입력한다. 출력 사람의 덩치 등수를 구해서 그 순서대로 첫 줄에 출력해야 한다. 단, 각 덩치 등수는 공백문자로 분리되어야 한다. python 1. 이중 for문으로 탐색한다. 2. 자신보다 큰 ..

문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 입력된다. 출력 가장 작은 생성자를 출력하고 생성자가 없으면 0을 출력한다. 1. 1부터 입력된 N까지 for문을 돌린다. 2. while문을 통해 각각의 수의 분해합을 만든다. 3. 분해합이 입력된 N과 같다면 result에 대입하고 for문을 종료한다. python num = int(input()) result = 0 for n in range(1,num): total = n _n = n..