투투

문제 로봇 청소기가 청소하는 영역의 개수 구하기 로봇 청소기가 이동할 수 있는 맵은 NxM 크기의 직사각형이고 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있고 상하좌우로 이동할 수 있다. 로봇 청소기는 다음과 같이 동작한다. 1. 현재 위치를 청소한다. 2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색 진행 2-1. 왼쪽 방향에 청소할 공간이 있으면 그 방향으로 회전한 다음 한 칸 전진후 1번부터 진행 2-2. 왼쪽 방향에 청소할 공간이 없다면 그 방향으로 회전 후 2번으로 돌아간다. 2-3. 네 방향 모두 청소가 되었거나 벽인 경우네는 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다. 2-4. 네 방향 모두 청소가 되었거나 벽이면서 뒤쪽 방향이 벽이라..

문제 신입사원을 채용하려고 할 때 서류심사 성적과 면접시험 성적을 고려한다. 이때 둘 중의 한 점수라도 다른 지원자보다 높다면 채용을 하게 된다. 즉 어떤 지원자가 자기보다 서류와 면접 성적이 높다면 그 지원자는 절대 채용될 수 없다. 이 회사가 채용할 수 있는 최대 사원의 수를 구하라. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫 N N은 1이상 100,000이하이다. 이후 N개의 서류심사 성적과 면접 성적 순위가 입력된다. 동석차는 없다. 출력 각 테스트 케이스마다 최대 인원 수를 출력 먼저 이런 수와 관련된 것들이 나열되어있으면 정렬을 한 다음에 풀면 어떨까? 라는 생각이 들었다. 그래서 서류심사 석차를 기준으로 오름차순 정렬을 했다. 그렇게 되면 첫..

문제 한 개의 회의실에서 N개의 회의를 진행하려고 한다. 각 회의는 시작시간과 끝나는 시간이 주어져있고 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 구하라 단, 회의는 한번 시작하면 중간에 중단되지 않으면 끝나는 시간과 동시에 다음 회의가 시작될 수 있다. 입력 첫째 줄에 회의의 수 N이 주어진다. 둘째 줄부터 회의의 시작시간과 끝나는 시간이 주어진다. 출력 회의의 최대 개수 출력 한 개만 있는 회의실에 어떤 회의를 진행시켜야 할까? 최대한 많은 회의를 해야 하기 때문에 회의가 끝날 때마다 다음 회의는 어떤 회의를 진행시킬지 생각해봐야 한다. 문제에서 주어진 것은 시작시간과 끝나는 시간이다. 먼저 매번 가장 빨리 시작하는 회의를 선택하면 어떨까? 빨리 시작할 수는 있지만 가장 ..

문제 동전을 적절히 사용해서 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하라. 입력 첫째 줄에 N과 K N은 1이상 10이하 K는 1이상 일억이하 둘째 줄부터 N개의 줄에 동전의 가치 A가 오름차순으로 주어진다. 출력 K원을 만드는데 필요한 동전 개수의 최솟값 출력 직관적으로 화폐가치가 높은 것으로 채워야 동전의 개수가 최소가 된다. 따라서 입력받은 N개의 동전을 내림차순으로 정렬하여 하나씩 꺼내어 나눠본다. 나누었을 때 1이상이면 나눈 몫을 최종해에 더하고 (몫x화폐가치)만큼 K원에서 빼준다. K가 0원이 되었을 때 반복문을 종료하도록 한다. #include "pch.h" #include #include #include using namespace std; int main()..

문제 한 대의 ATM기기 앞에 N명의 사람들이 줄 서 있으며 각 사람들이 돈을 뽑는 시간은 다르다. 만약 첫 번째 사람이 2분 두 번째 사람이 3분이라면 두 번째 사람은 총 5분이 소요되고 첫 번째 사람은 2분이 소요되어 두 사람이 모두 돈을 뽑으려면 7분이 걸리게 된다. 이처럼 N명의 사람이 돈을 뽑을 때 최소한의 시간으로 뽑을 수 있는 시간은 몇인지 구하라 입력 첫째 줄에 사람의 수 N(1이상 1000이하) 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간을 입력한다.(1이상 1000이하) 출력 사람들이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력 만약 5분이 걸리는 사람과 1분이 걸리는 사람이 있을 때 5분이 걸리는 사람이 먼저 뽑게되면 두 번째 사람은 6분이 소요된다. 따라서 시간이 적게 ..

문제 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은 빈 칸이고 벽을 세울 수 있는 ..