본문 바로가기

전체 글143

DP 문제 해결 - 백준 극장 좌석 문제 https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 문제 - 어떤 극장의 좌석은 한 줄로 되어 있으며 - 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. - 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. - 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. - 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. - 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 .. 2023. 5. 15.
이진탐색 문제 해결 - 백준 용돈 관리 문제 https://www.acmicpc.net/problem/6236 - 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. - 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다. - 현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. - 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도, 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다. - 현우는 돈을 아끼기 위해 인출 금액 K를 최소화하기로 하였다. - 현우가 필요한 최소.. 2023. 5. 15.
정렬 문제 해결 - 프로그래머스 K번째 수 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42748 - 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 한다. - 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i=2, j=5, k=3이라면 1. array의 2(i)번째부터 5(j)번째까지 자르면 [5, 2, 6, 3]이다. 2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]이다. 3. 2에서 나온 배열의 3(k)번째 숫자는 5이다. - 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, - commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온.. 2023. 5. 15.
DFS 문제해결법 문제 - 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. - 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. - 창고가 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. - 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. - 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. - 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. - 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다. - 토마토를 창고에.. 2023. 5. 9.

티스토리툴바