작심 24/7

14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 단순한 DFS 문제인 줄 알고 대충 읽고 짜다가 갈아엎었다. 시뮬레이션 문제이므로 작동 순서를 잘 읽고 구현해야 한다. 1. 현재 방향에서 왼쪽 방향으로 일단 회전하고 그 방향의 공간이 비어있는지 확인한다. 2. 청소하지 않은 빈 공간이라면 -> 전진한다. (재귀) 벽이거나 청소를 한 공간이라면 -> 왼쪽 방향으로 한 번 더 회전한다. 3. 왼쪽 방향으로 총 네 번 회전하며 확인했는데도 빈 공간이 없을 경우 현재 방향은 그대로 뒤로 후진한다. 4. 후진할 공간이..

15748번: Rest Stops The first line of input contains four integers: $L$, $N$, $r_F$, and $r_B$. The next $N$ lines describe the rest stops. For each $i$ between $1$ and $N$, the $i+1$-st line contains two integers $x_i$ and $c_i$, describing the position of the $i$-th rest st www.acmicpc.net 가치가 가장 큰 stop부터 가야 하므로 가치를 기준으로 내림차순 정렬한다. stop에서 Bessie가 쉴 수 있는 시간은 (John의 1미터 당 걸리는 시간 - Bessie의 1미터 당 걸..

1493번: 박스 채우기 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, www.acmicpc.net 탐욕법으로 가장 큰 큐브부터 박스에 넣어본 후 남은 부분들을 세 가지로 나누어 재귀로 계속 반복한다. 그림과 같이 현재 가장 큰 큐브 l, w, h를 제외하고 남은 1번, 2번, 3번 상자들은 각각 다시 하나의 상자로 생각하여 현재 가장 큰 큐브를 제외하고 남은 세 가지 상자들을 다시 각각 하나의 상자로 생각하고 ... 이 과정을 가로, 세로, 높이 중 하나라도 0이 될 때까지 계속 반복한 후 빠져나와서 카운트를 출력한다. 가로..

13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 점수를 최대한 많이 받아야 하기 때문에 점수를 기준으로 내림차순 한 후 score 배열을 만들어 마감일에 따라 받을 수 있는 점수를 저장한다. W D 60 4 50 2 40 4 30 3 20 1 10 4 5 6 내림차순 한 상태에서 첫 번째 인덱스부터 score 배열에 넣으면 score[4] = 60 '4일 안에 과제를 하면 60점을 얻는다' 라는 의미이다. 마찬가지로 두 번째 인덱스도 score 배열에 넣으면 score[2] = 50 이 된다. 세 번째 인덱스를 score 배열에 넣으려 하니 score[4..

1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 제품 사용 순서대로 돌면서 세 가지 경우를 확인해주고 그 경우에 따라 처리해주면 된다. 1. 현재 제품이 멀티탭에 꽂혀있을 경우 -> 그냥 넘어간다. 2. 멀티탭이 다 안 채워져 있을 경우 -> 현재 제품의을 저장한다. 3. 플러그를 뽑아야하는 경우 -> 남은 순서동안 멀티탭에 꽂혀있는 제품을 쓰지 않는다면 그 제품의 플러그를 뽑는다. -> 남은 순서동안 멀티탭에 꽂혀있는 제품이 모두 쓰인다면 가장 마지막으로 쓰이는 제품의 플러그를 뽑는다. 이대로 구현해주면 끝..

11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net LIS 변형 문제이다. LIS는 DP 배열에 증가 부분 수열의 길이를 갱신하는 반면 이 문제는 같은 증가 부분 수열 내의 원소들의 합을 갱신시키고 각 증가 수열이 끝날 때마다 최댓값을 갱신시켜준 뒤 최종 최댓값을 출력시키면 된다. #include #include using namespace std; int main() { int N, Max = -1; int A[1001], dp[1001]; cin >>..

12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 주어진 무게들과 그에 따른 가치들을 pair로 벡터에 넣고 오름차순으로 정렬한다. 이차원 배열 DP를 만들어 0/1 Knapsack 원리로 구현한다. 평범한 배낭과 동전 문제와 비슷한 개념인데 차이점은 동전은 같은 동전을 여러 개 쓸 수 있다는 것이고 평범한 배낭은 이 물건을 가져가거나, 가져가지 않거나. 이 두가지 선택지밖에 없다는 것이다. 그래서 문제에 있는 예제로 표를 채워보면 가치 무게 1 ..

11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 파스칼의 삼각형에서 도출해낼 수 있는 이항 계수의 공식은 이다. 그런데 이대로 구현하면 nCr=nCn-r 이라는 성질 때문에 예를 들면 5C1 5C2를 구했는데 같은 값인 5C4, 5C3도 구하게 되는 불필요한 계산을 하게 된다. 그래서 삼각형을 반으로 나누어 중복되는 값을 없애보았다. 이렇게 반으로 나누면 짝수일 때 마지막 숫자만 이렇게 되고 나머지는 이 공식이 똑같이 적용된다. 이대로 구현해주면 끝 #include using namespace std; int main() { int N, K; cin >> N >> K; int dp..