CodeDrive

문제:

풀이방법:

 시간은 한정되어 있기 때문에 모든 케이스를 다 고려하는 방법으로 문제를 해결했다. 최대로 필요한 객실의 수는 입력으로 들어오는 book_time의 길이와 같다. 따라서 book_time의 높이와 시간의 길이를 가지는 배열(hotel)을 만들도록 한다.

 그리고 각 예약 손님이 사용하는 길이를 hotel 배열에 기록한다. 이 때, 10분간 청소를 하는 시간 또한 같이 고려하도록 한다. 모든 예약 손님에 대해 기록을 완료했다면 세로로 hotel 배열을 탐색하며 가장 많이 겹치는 구간을 답으로 선정한다.

문제링크:

https://school.programmers.co.kr/learn/courses/30/lessons/155651

문제:

찬솔이는 블로그를 시작한 지 벌써 N일이 지났다.

요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.

찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.

찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자.

입력:

첫째 줄에 블로그를 시작하고 지난 일수 N와 X가 공백으로 구분되어 주어진다.

둘째 줄에는 블로그 시작 1일차부터 N일차까지 하루 방문자 수가 공백으로 구분되어 주어진다.

출력:

첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다.

만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다.

풀이방법:

X만큼의 구간을 슬라이딩 하면서 최댓값을 갱신하고, 최댓값이랑 같은 경우에는 기간을 증가시켜준다.

문제링크:

https://www.acmicpc.net/problem/21921

문제:

풀이방법:

우선 한쪽으로 케이크의 모든 토핑을 모아두고, 하나씩 반대로 옮기면서 갯수가 같아지는 지점을 체크하도록 한다.

 이 과정을 편하게 하기 위해 dict 자료형을 선택했고, collections의 defaultdict을 사용했다. defaultdict은 dict의 key 초기화 과정이 필요하지 않다는 장점이 존재한다.

 따라서 하나씩 토핑을 제거하고, 제거한 토핑은 반대 dict의 넘겨준다. 만약 value가 0이 된다면 key를 제거한다. 이렇게 했을 때, 두 dict의 key의 길이가 같다면 공평하게 자르는 방법이라고 생각한다.

문제링크:

https://school.programmers.co.kr/learn/courses/30/lessons/132265

문제:

IQ Test의 문제 중에는 공통된 패턴을 찾는 문제가 있다. 수열이 주어졌을 때, 다음 수를 찾는 문제이다.

예를 들어, 1, 2, 3, 4, 5가 주어졌다. 다음 수는 무엇인가? 당연히 답은 6이다. 약간 더 어려운 문제를 보면, 3, 6, 12, 24, 48이 주어졌을 때, 다음 수는 무엇인가? 역시 답은 96이다.

이제 제일 어려운 문제를 보자.

1, 4, 13, 40이 주어졌을 때, 다음 수는 무엇일까? 답은 121이다. 그 이유는 항상 다음 수는 앞 수*3+1이기 때문이다.

은진이는 위의 3문제를 모두 풀지 못했으므로, 자동으로 풀어주는 프로그램을 작성하기로 했다. 항상 모든 답은 구하는 규칙은 앞 수*a + b이다. 그리고, a와 b는 정수이다.

수 N개가 주어졌을 때, 규칙에 맞는 다음 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 N개의 수가 주어진다. 이 수는 모두 절댓값이 100보다 작거나 같은 정수이다.

출력:

다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다.

풀이방법:

문제에서 찾아야 하는 a와 b를 찾는 것은 연립방정식을 사용한다면 쉽게 찾을 수 있다. 하지만 A, B와 같이 특이 케이스들이 다수 존재하기 때문에 이를 위한 노력이 필요하다. 다음과 같은 케이스들이 존재할 수 있다.

1. N이 1인 경우

N이 1인 경우에는 a와 b를 알 수 없기 때문에 다음에 여러 수가 존재할 수 있다. -> A

2. N이 2인 경우

N이 2인 경우에도 a와 b를 알 수 없기 때문에 여러 수가 존재할 수 있다.(A) 하지만 첫 두 수가 같다면 a=1, b=0인 특수한 케이스에 해당하기에 마지막 수를 출력한다.

3. N이 3 이상인 경우

 N이 3 이상이면 연립방정식을 통해 a와 b를 구할 수 있게 된다. 따라서 첫 세 수를 사용하여 a와 b를 구하도록 한다. 이 때, a와 b를 정수라는 조건이 있기 때문에 소수가 구해지게 된다면 B를 출력하도록 한다.

 a와 b를 정상적으로 구해도 첫 세 수를 통해 구한 값이기 때문에 이 규칙이 주어진 배열 끝까지 동작하는지 확인하는 작업이 필요하다. 규칙이 정상적으로 작동한다면 규칙을 사용하여 다음 수를 출력하고, 그렇지 않다면 B를 출력한다.

문제링크:

https://www.acmicpc.net/problem/1111

문제:

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다.

출력:

첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

풀이방법:

X인 부분을 그리디하게 채워나가도록 한다. X가 4개이상이라면 AAAA로 채우고, 4개 미만이라면 BB로 채우도록 한다. 이 때, X가 남은 경우 혹은 X가 부족한 경우가 덮을 수 없는 케이스라고 판단한다.

문제링크:

https://www.acmicpc.net/problem/1343

문제:

NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.

시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.

시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과 열의 위치를 의미하며, 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당한다.

예를 들어 다음과 같이 3x3 크기의 시험관이 있다고 하자. 서로 다른 1번, 2번, 3번 바이러스가 각각 (1,1), (1,3), (3,1)에 위치해 있다. 이 때 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류를 계산해보자.

1초가 지난 후에 시험관의 상태는 다음과 같다.

2초가 지난 후에 시험관의 상태는 다음과 같다.

결과적으로 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류는 3번 바이러스다. 따라서 3을 출력하면 정답이다.

입력:

첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분되어 주어진다. 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어진다. 또한 모든 바이러스의 번호는 K이하의 자연수로만 주어진다. N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)

출력:

S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력한다. 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.

풀이방법:

 바이러스 번호가 낮은 것부터 2차원 배열에 확산시키는 문제로 너비 우선 탐색에 해당한다. 처음에는 시간을 고려하지 않고, 너비 우선 탐색만 생각하고 문제를 풀려고 했으나 계속해서 시간초과가 발생하게 되었다.

 처음 생각했던 방법은 중복으로 탐색하는 경우도 많았으며, 이미 다 채워져 있었는데 시간(S)이 남았다는 이유로 계속 2차원 배열 탐색을 계속했기 때문에 시간초과가 발생했던 것으로 보인다. 

 그래서 deque에 바이러스 종류, 시간, 좌표등을 모두 저장하고 이를 기준으로 바이러스를 증식시키는 것으로 수정하게 되었다. 초기 시험관을 받고 바이러스 정보를 모두 deque에 넣고 정렬하면 낮은 종류의 바이러스부터 먼저 증식시킬 수 있다.

문제링크:

https://www.acmicpc.net/problem/18405

문제:

풀이방법:

처음에 문제를 이해하는 것이 가장 어려웠던 것 같다. 다음과 같은 흐름으로 문제를 이해하면 도움이 될 것 같다.

• 택배 상자는 무조건 [1,2,3,4, ... ] 와 같은 순서로 주어진다.
  • 택배 기사님의 순서와는 무관하다.
• 문제의 설명을 보면 Stack을 사용해야 한다. 이 때, 컨테이너 벨트(main), 보조 컨테이너 벨트(sub) 모두 stack으로 이루어진 배열이다.
  • 단, 컨테이너 벨트에는 [1,2,3,4, ...]가 이미 적재되어 있다.
• main에서 sub로 이동하는 것은 가능하지만, sub에서 main으로 이동하는 것은 불가능하다.

결국 2개의 stack 배열을 사용해서 택배 기사님의 순서를 맞추는 문제라고 생각하면 된다.

 main에서 sub로만 이동하는 것이 가능하기 때문에 main 혹은 sub의 out 상자가 첫 택배 기사님의 순서에 맞게 세팅을 해둔다. 택배 기사님이 원하는 택배 상자를 적재 하고 main이나 sub에 또 원하는 상자가 있다면 연속해서 적재하며 만약 그렇지 않다면 main에서 sub로 이동시키며 조건을 만족하는지 계속해서 확인한다.

 이 과정을 main의 모든 택배 상자가 비었으며, 더 이상 적재하지 못할 때까지 반복한다.

문제링크:

https://school.programmers.co.kr/learn/courses/30/lessons/131704

문제:

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.

어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. i는 0부터 시작한다.

출력:

첫째 줄에 줄을 선 순서대로 키를 출력한다.

풀이방법:

 이 문제는 그리디하게 채워나가는 것을 목표로 한다. 우선 N과 같은 길이의 0으로 채워진 배열(answers)을 생성한 후 다음과 같은 조건으로 채워나간다.

1. 현재 answers 인덱스에 이미 사람이 채워져 있는가?
2. 만약 비어있다면, 내가 들어갈 차례인가?
   1. 비어있던(answers가 0) 횟수가 내 순서와 같은가?

 즉, answers가 0인 경우에 자기보다 큰 사람이 들어갈 자리라고 생각하며, 이 자리를 미리 고려하면서 빈 자리에 들어가는 것을 선택한다.

문제링크:

https://www.acmicpc.net/problem/1138

문제:

시골에 있는 태양이의 삼촌 댁에는 커다란 참외밭이 있다. 문득 태양이는 이 밭에서 자라는 참외가 도대체 몇 개나 되는지 궁금해졌다. 어떻게 알아낼 수 있는지 골똘히 생각하다가 드디어 좋은 아이디어가 떠올랐다. 유레카! 1m2의 넓이에 자라는 참외 개수를 헤아린 다음, 참외밭의 넓이를 구하면 비례식을 이용하여 참외의 총개수를 구할 수 있다.

1m2의 넓이에 자라는 참외의 개수는 헤아렸고, 이제 참외밭의 넓이만 구하면 된다. 참외밭은 ㄱ-자 모양이거나 ㄱ-자를 90도, 180도, 270도 회전한 모양(┏, ┗, ┛ 모양)의 육각형이다. 다행히도 밭의 경계(육각형의 변)는 모두 동서 방향이거나 남북 방향이었다. 밭의 한 모퉁이에서 출발하여 밭의 둘레를 돌면서 밭경계 길이를 모두 측정하였다.

예를 들어 참외밭이 위 그림과 같은 모양이라고 하자. 그림에서 오른쪽은 동쪽, 왼쪽은 서쪽, 아래쪽은 남쪽, 위쪽은 북쪽이다. 이 그림의 왼쪽위 꼭짓점에서 출발하여, 반시계방향으로 남쪽으로 30m, 동쪽으로 60m, 남쪽으로 20m, 동쪽으로 100m, 북쪽으로 50m, 서쪽으로 160m 이동하면 다시 출발점으로 되돌아가게 된다.

위 그림의 참외밭  면적은 6800m2이다. 만약 1m2의 넓이에 자라는 참외의 개수가 7이라면, 이 밭에서 자라는 참외의 개수는 47600으로 계산된다.

1m2의 넓이에 자라는 참외의 개수와, 참외밭을 이루는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나는 변의 방향과 길이가 순서대로 주어진다. 이 참외밭에서 자라는 참외의 수를 구하는 프로그램을 작성하시오.

입력:

첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나는 변의 방향과 길이 (1 이상 500 이하의 정수) 가 둘째 줄부터 일곱 번째 줄까지 한 줄에 하나씩 순서대로 주어진다. 변의 방향에서 동쪽은 1, 서쪽은 2, 남쪽은 3, 북쪽은 4로 나타낸다.

출력:

첫째 줄에 입력으로 주어진 밭에서 자라는 참외의 수를 출력한다.

풀이방법:

 참외밭의 모양은 ㄱ-자 이거나 해당 모양의 회전 형태로 구성되어 있다. 이러한 모양의 넓이는 구하는 방법은 아래 그림을 참고하면 쉽게 구할 수 있다.

 이 문제에서 원하는 넓이는 노란색 영역의 넓이다. 해당 넓이를 (노랑+빨강) 직사각형에서 빨강의 직사각형을 빼는 방식으로 쉽게 구할 수 있다. 따라서 이 문제에서 해야할 것은 가장 긴 가로 길이와 가장 긴 세로 길이를 구하고, 이를 통해 작은 직사각형의 넓이를 구하는 것이다.

 입력으로 주어진 방향과 길이 배열을 한번씩 순회하면서 가장 긴 가로, 세로 길이를 구하고 배열의 인덱스를 저장한다. 그러면 가장 긴 가로, 세로 인덱스를 기준으로 양 옆의 길이 차를 계산하면 작은 직사각형의 가로 및 세로 길이를 구할 수 있게 된다.

 최종적으로 큰 직사각형과 작은 직사각형의 가로, 세로 길이를 모두 알 수 있게 되었으므로 이 둘의 차를 구한 뒤 K 값을 곱해주도록 한다.

문제링크:

https://www.acmicpc.net/problem/2477

문제:

2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다.

진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다.

하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다.

꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다. 꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다.

꽃을 심을 때는 주의할 점이있다. 어떤 씨앗이 꽃이 핀 뒤 다른 꽃잎(혹은 꽃술)과 닿게 될 경우 두 꽃 모두 죽어버린다. 또 화단 밖으로 꽃잎이 나가게 된다면 그 꽃은 죽어버리고 만다.

그림(c)는 세 꽃이 정상적으로 핀 모양이고 그림(d)는 두 꽃이 죽어버린 모양이다.

하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다.

단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다.

돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자!

입력:

입력의 첫째 줄에 화단의 한 변의 길이 N(6≤N≤10)이 들어온다.

이후 N개의 줄에 N개씩 화단의 지점당 가격(0≤G≤200)이 주어진다.

출력:

꽃을 심기 위한 최소 비용을 출력한다.

풀이방법:

화단의 한 변의 길이가 가장 큰 경우는 10이며, 꽃은 3개를 심을 수 있다. 이 때 양 끝 라인들은 꽃을 심을 경우 화단 밖으로 꽃잎이 나가게 되므로, 심지 못하는 구간이다. 따라서 8x8의 점에서 3개를 선택하는 것과 같다. 많지 않은 케이스를 가지고 있으므로, 모든 경우의 수를 구하고, 가능한지 여부를 파악한다. 그래서 가능한 경우에 비용만을 체크하여 최소 비용을 찾는다.

 따라서 combination을 사용하여 모든 케이스를 확인하고, 각 케이스에 대해 한 번의 BFS를 수행하여 겹치는 점이 있는지 확인하도록 한다. 겹치면 다음 케이스로 넘어가고, 없다면 최소비용을 업데이트하도록 한다.

 모든 케이스를 확인하고, 비용을 출력하도록 한다.

문제링크:

https://www.acmicpc.net/problem/14620