방배동 고구마

문제 벽돌쌓기를 하자. 인부들이 N명 있고 벽돌 쌓기를 할 작업 갯수가 T만큼 있다. 한명의 인부가 A번 만큼 작업을 하게 되면 R만큼 쉬는시간을 부여한다. 또한 작업 개수 T만큼의 작업 시간이 주어진다. 위의 규칙으로 작업을 할 때 작업이 끝날때까지의 시간을 구하라. 예를 들어 3명의 인부(N=3), 10개의 작업(T=10), 휴식까지 3번의 작업(A=3), 쉬는 시간 2(R=2)라고 주어지고 각 작업시간이 1 2 1 4 3 2 1 5 2 3 라고하면 작업시간표는 아래와 같다. 작업시간은 10 N이 2, T가 8, A가 3, R이 2이고 작업시간이 각각 2 3 4 1 1 5 4 2 일 경우는 아래와 같다. 작업 시간은 13 입력 case1 3 10 3 2 1 2 1 4 3 2 1 5 2 3 case2 ..

문제 아이템을 먹어주는 프로그램을 만들려고 한다. 단, 아이템을 먹는 규칙이 있다. 바닥에 떨어져 있는 아이템을 1번 부터 N번까지 있을때, S번의 아이템부터 시작하여 M번째 아이템을 먹는다. 그 후 다음 번호의 아이템부터 셈하여 M번째 아이템을 먹게 된다. 아이템을 먹게되는 순서를 구하라. 예를들어 아래와 같다고 하자. S가 1이고 M이 4이므로 가장 먼저 먹을 수 있는 아이템은 4이다. 이후 4 다음인 5부터 M번째 아이템은 1이므로 두번째 먹을 수 있는 아이템은 1이다. 다음으로 먹게 될 아이템은 1이다. 이와 같은 순서로 다음은 6, 5, 7, 3, 2의 순서로 아이템을 먹게 된다. 입력 N개의 아이템이 입력되며 N은 1부터 10000개이다. 시작하는 아이템 번호가 S로 입력되며 S는 1부터 N까..

문제 N개의 샘플이 있고 각각의 샘플에는 정수가 주어진다. 연구를 위해 N개중 2개의 샘플을 채취한다. 이때 샘플이 가진 정수의 합이 0에 가까운 2개의 샘플을 채취하고자 한다. N(2~100000), 정수A(-1000000 ~ +1000000) 이며 샘플의 정수 값으 오름차순으로 입력된다고 한다. 0에 가까운 값이 여러 경우일 경우 가장 빠른 번호의 샘플을 답으로 한다. 위 조건에 맞는 2개의 샘플 번호를 구하라 입력 5 -102 -58 59 78 101 출력 0 4 문제해결 조합 문제이다. N개의 샘플중 2개의 샘플을 고른다. 순서는 상관이 없다. 트리를 구성하는 DFS로 모든 경우의 수를 수행할 수도 있지만 N이 10만개이므로 시간복잡도 N제곱으로 timeout일 경우가 생긴다. 따라서 DFS는 적..

스택문제는 참으로 까다롭다. 경험으로 봤을때는 코드로 만들고나서 반드시 Test case를 손으로 똑같이 해봐야 하는 거 같다. 그래야 문제점을 발견할 수 있다. 또한 스택처리 반복안에서 분기를 치거나 첫노드를 먼저 Push하거나 하는 것은 좋지 못하다. 스택처리 반복이 복잡해질 수록 추적하기 어렵기 때문이다. 간단한 스택처리 Test case로 한줄한줄 한손한손 따라가면서 디버깅해보자. 문제 높이가 다른 N개의 전봇대가 주어진다. 서로다른 전봇대끼리 전깃줄을 잇는다. 1. 이웃한 두개의 전봇대는 전깃줄을 잇는 것이 무조건 가능하다. 2. 이웃하지 않은 두개의 전봇대 사이에 양측의 두 전봇대보다 높이가 높거나 같다면 전깃줄을 이을 수 없다. 위의 그림의 경우 5가지의 경우가 있다. 1번과 3번 전봇대는 ..

논리문제는 아이디어를 내기까지가 상당히 까다롭다. 결국 많은 경험이 필요하다. 다음 문제를 보자 문제 N*N의 영역이 주어진다.(N : 2~10000) 해당 영역에 먼지가 떨어져 있다. 청소를 단 한번 할 수 있다. 청소 구역의 둘레 길이 L(4~100이며 짝수이다)이 주어진다. 먼지의 개수는 M(1~100)으로 주어지며 먼지의 X,Y좌표값이 주어진다. 주어진 L의 조건에서 청소 시 가장 많이 제거할 수 있는 먼지의 갯수를 구하라 입력 6 10 6 2 2 4 6 5 2 6 4 2 4 3 3 출력 4 접근방법 주어진 케이스는 아래와 같다. 청소영역 둘레가 10이라 청소영역 가로세로 2*3 조합도 가능하고 1*4 조합도 가능하다. 아이디어를 생각해본다. 1) 간단하게 N을 기준으로 모든 영역을 수행한다. N..

[문제] N*N(N : 4~ 10) 크기의 도화지에 색종이를 붙인다. 색종이는 직사각형 모양이다. 이때 겹쳐 붙일 수 있다. 색종이는 숫자 1부터 9까지 나타나며 빈 도화지는 0으로 나타낸다. 가장 많이 겹쳐진 지점의 색종이 수를 구하라. [입력] 4 1591 1496 1444 0550 [출력] 4 [접근방법] 주어진 입력을 그림으로 표현하면 아래와 같다. 앞선 덧칠 문제와 굉장비 비슷한 접근 방법이다. 1. 색깔 별로 minX, minY, maxX, maxY의 값을 구한다. for문으로 탐색하여 좌표별 최고 최소 값을 구하면 될것이다. 2. 구한 좌표를 저장해둔다. 구조체 배열을 사용하면 편리하겠다. 3. 저장된 좌표값을 차례로 visit 배열에 count올린다. 4. visit배열에 가장 큰 값을 찾..

문제 꼬리잡기 게임을 한다. 일직선 상에서 진행하며 모두 동시에 출발하지만 출발 위치와 속도는 다르다. T분동안 게임이 진행되며 일직선 상이기 때문에 추월할 수 없고 속도가 빠른 뒷사람의 앞사람의 꼬리를 잡으면 하나의 그룹으로 인식된다. 주어진 조건에서 몇개의 그룹이 형성되는지 구하라 입력 참가자 수 N : 1~100,000 게임시간 T : 1~1,000,000,000 각 참가자출발 위치 P : 0 ~ 1,000,000,000 각 참가자 속도 S : 0 ~ 1,000,000,000 ※ 출발위치는 오름차순으로 입력됨 5 3 0 1 1 2 2 3 3 2 6 1 출력 3 접근방식 아주 간단하게 생각해보자. 1. 각 참가자의 계산된 T분 후 위치를 구한다.2. 뒷 사람이 앞사람보다 위치가 클 경우, 앞사람의 위..