AndroidTeacher

www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 설명 ATM기 앞에 사람이 N명 서있는데, 이 N명의 사람들이 돈을 인출하는데 걸리는 시간은 제각각이다. 이 때, 앞 사람의 돈을 뽑는 시간이 길 수록, 뒤에 있는 사람들의 대기 시간은 길어지게 된다. 각 사람이 돈을 인출하는데 필요한 시간(대기시간+뽑는시간)의 합의 최솟값을 구하면 된다. 풀이 과정 내가 ATM기에 줄을 서 있다고 가정해보자. 나의 대기시간이 짧아지려면 어떤 상황이 되어야 하는가? 당연히 내 앞에서 돈을 뽑는 사람들이..

www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 설명 한 개의 회의실에서 N개의 회의가 이루어진다. 각각의 회의 I에 대해 시작시간과 끝나는 시간이 주어지며, 각 회의실은 겹쳐서 사용할 수 없다. 단, 끝나는 즉시 다음 회의가 시작을 이어받을 수 있으며, 시작 시간과 끝나는 시간이 같을 수도 있다.( 시작 즉시 종료 ) 이 때, 열릴 수 있는 회의의 최대 갯수를 구하면 된다. 풀이 과정 대표적인 그리디 개념을 이용하는 문제이다. 그리디는 당장의 상황을 기준으로 확장시키는 방향으로 풀면 쉽게 해결이 가능한 경우가 많다. 내가 회의실을 사용하고 있다고 가정했을 때, 내 회..

www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 설명 N종류의 동전으로 K원을 만들 때, 동전 개수의 최솟값을 구하는 문제이다. 풀이 과정 먼저 coin 리스트에 코인들을 오름차순으로 입력받게 되는데, 가장 적은 수의 코인을 갖기 위해서는 단위가 큰 코인부터 채워야 한다. 따라서 coin을 내림차순 정렬해주고 하나씩 차례대로 계산을 해주면 된다. K원을 현재 코인으로 나눈 값의 몫을 누적해..

www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 문제 설명 문제에서 말한 이분그래프란, 그래프 정점의 집합을 둘로 나눴을 때, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프를 말한다. 즉, 그래프의 정점을 두가지 색으로 칠할 때, 인접한 정점끼리는 다른 색을 가지고 있는 그래프 인 것이다. 위 그림은 대표적인 이분그래프이다. 풀이 과정 visited[V]에 1, 2의 값을 줌으로써 정점의 색을 구분한다. ( 단, 아직 미..

문제 설명 www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 체스판 위의 나이트가 최소 몇번을 움직여 도착지까지 이동할 수 있는지를 구하는 문제이다. 풀이 과정 나이트가 이동할 수 있는 경로는 체스의 나이트와 똑같이 가로2칸 이동후 세로1칸 혹은 가로1칸 이동 후 세로1칸 이기 때문에 8가지 상황이 발생한다. visited의 각 칸에는 그 칸까지 오는데 필요한 횟수가 저장되어 있으며 초기는 모두 0으로 저장되어 있다. 즉, 아직 밟지않은 칸은 모두 0으로 초기화..

문제 설명 www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net N×M의 행렬로 표현되는 맵에서 0은 이동할 수 있는칸, 1은 벽(이동할 수 없는 칸)을 나타낸다. 단, 벽을 부수고 이동할 수 있는 기회가 1번 주어지므로 부셨을 때 이동경로가 짧아진다면 부셔도 된다. (1, 1)에서 시작하여 (N,M)까지 가는데 최단거리를 출력하면 된다. 풀이 과정 전형적인 BFS 의 경로찾기 문제에 벽을 부술 수 있다는 특징이 포함된 문제이다. 중간에 ..

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 설명 수빈이는 동생과 숨바꼭질을 한다. 수빈이의 좌표는 N, 동생의 좌표는 K이다. 수빈이의 위치가 X일 때, 1초 후에 X+1, X-1 X*2 중에 하나로 이동할 수 있다. 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초인지를 구하면 된다. 풀이 과정 BFS를 이용하여 풀었다. 변수에 대해 먼저 설명하자면, count는 일 수, flag는 찾은 여부를 나타내는 변수이다...

www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 설명 가로 M, 세로 N 의 토마토 상자가 H높이만큼 쌓여져 있다. 즉 3차원 배열의 형태로 쌓여져 있다. 이 토마토는 보관 후 하루가 지나면 익은 토마토들의 인접(상하좌우위아래)한 토마토들이 모두 익게 된다. 이 토마토들이 모두 익게되는데 며칠이 걸리는지 최소 일수를 구하면 된다. 풀이 과정 토마토들의 좌표는 graph[x][y][z]로 나타낼 수 있다. 기존 문제들과의 차이점이라..

www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 설명 R x C 크기의 보드판이 있다. 이 보드판의 각 칸에는 대문자 알파벳이 하나씩 적혀있으며, 이 보드판을 움직이는 말은 현재 (1,1)에 위치하고 있다. (시작점에 위치) 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있으며, 새로 이동하는 칸에 적힌 알파벳은 지금까지 지나온 알파벳과 겹쳐서는 안된다. 즉, 같은 알파벳 칸을 두 번 이상 지나갈 수 없다. 좌측 상단부터 시작하여 말이..

www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 문제 설명 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다. 예를 들어, A = {10, 20, 10, 30, 20, 50} 인 경우 가장 긴 증가하는 부분 수열은 {10, 20, 30, 50} 이다. 풀이 과정 먼저, 풀이과정 두가지를 이용할 수 있는데, 하나는 이진탐색을 직접 구현하여 수열이 들어갈 자리를 찾는 방법이고 다른 하나는 내장 모듈인 bisect를 이용한 방법이다. 먼저 풀..