간타타 공부장 간타타 공부장

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감�� www.acmicpc.net 아이디어 1, 위, 아래, 왼쪽, 오른쪽을 감시 할 때의 기능을 하는 함수를 각각 구현 2, cctv의 종류에 따라 감시할 수 있는 방향의 모든 경우를 고려하여 dfs를 구현 3, 단, 이때 주의할 점은 dfs를 구현 할 때 이전 상태로 되돌릴 때, 해당 cctv가 감시를 했던 곳만 이전 상태로 되돌려야 한다. 즉, 감시가 겹쳐있는 곳이 있기 때문에 구분을 잘 해 주워야 한다. #i..

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 아이디어 1, 각각의 톱니의 상태를 deque로 저장을 한 다음 시계방향과 반시계 방향으로 돌았을 때의 기능을 하는 함수 구현 2, 한번의 회전이 진행이 되고 새롭게 각각의 톱니들이 맞물려 있는 상태를 갱신하는 함수 구현(다음번 회전을 할 때 회전에 대한 유무를 조사) 3, 조건에 맞게 시뮬레이션을 진행 #include #include #include #include #include #incl..

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 아이디어 행과 열에 한 줄에 대하여 양 옆으로 한번씩 조사를 하면서 길이 될지 조사를 함 1, 행 - 왼쪽에서 오른쪽으로 가는 길을 조사를 하고 올라가는 경우에 대하여 길이 l에 대하여 조사를 함 - 내려가는 길에 대하여는 높이차이가 1인 경우에만 길조건 조사를 함 - 마찬가지로 오른쪽에서 왼쪽으로 가는 길을 조사를 마찬가지 방법으로 수행을 함 (이때, 왼쪽에서 오른쪽으로 가면서 올라가기 위해 경사로를 놓은 부분을 표시..

https://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 아이디어 방법1 dfs를 이용하여 팀이 될 수 있는 모든 경우의 수를 구한 다음 능력치의 차이를 계산 - 기존 시작 시에는 다들 0번 팀이라고 배치하고 팀을 부여함 - 재귀문을 통하여 한사람씩 1번 팀을 경우의 수마다 부여를 하고 해당 인원의 반이 1번팀의 배치가 되었으면 능력치 차이를 계산 방법2 비트 마스킹 방법을 이용하여 팀을 구분한 다음 능력치의 차이를 계산 -예시 : 110100 - 오른쪽부터 왼쪽 순으로 사..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 아이디어 1, dfs로 숫자를 돌면서 연산자가 들어 갈 수 있는 모든 경우의 수를 탐색하면서 만들 수 있는 최대값과 최소값을 구한다. #include #include using namespace std; int max_num = -1000000001; int min_num = 1000000001; int num; vector num_ar..

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net 11053번 가장 긴 증가하는 부분 수열과 비슷한 문제 아이디어 1, dp의 개념으로 시간 복잡도 O(n^2)로 풀이가 가능 2, , 해당 배열의 숫자를 왼쪽부터 오른쪽으로 순회를 하면서 dp배열에 해당 숫자를 끝으로 증가하는 부분 수열을 만들었을 때 합의 최댓값을 누적하여 저장한다. 예시 5번째의 숫자까지의 증가하는 부분 수열로 만들 ..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 아이디어 1, LIS기초 문제 2, dp의 개념으로 시간 복잡도 O(n^2)로 풀이가 가능 3, 해당 배열의 숫자를 왼쪽부터 오른쪽으로 순회를 하면서 dp배열에 그 숫자가 들어갈 수 있는 최대 index를 구한다. 예시 5번째의 숫자의 최대 index값을 구하고자 하면 0~4까지의 dp배열을 순회하면서 5번째의 숫자보다..

해당 문제 링크 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 아이디어 1, 시뮬례이션 문제 2, 서쪽, 동쪽, 북쪽, 남쪽으로 각각 주사위를 굴릴 경우 주사위의 상태를 저장해 주고 지도의 상태를 갱신하여 준다. 예시) 만약 주사위를 남쪽으로 굴렸을 경우 윗쪽 -> 앞쪽으로 앞쪽 -> 아래쪽으로 아래쪽 -> 뒷쪽 뒷쪽 -> 윗쪽 굴린이후 해당 문제의 조건의 맞게 지도 혹은 주사..