알고리즘 스터디 11주차

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

19941번: 햄버거 분배

문제

기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 K 이하인 햄버거를 먹을 수 있다.

햄버거	사람	햄버거	사람	햄버거	사람	햄버거	햄버거	사람	사람	햄버거	사람
1	2	3	4	5	6	7	8	9	10	11	12

위의 상태에서 K=1인 경우를 생각해보자. 이 경우 모든 사람은 자신과 인접한 햄버거만 먹을 수 있다. 10번의 위치에 있는 사람은 11번 위치에 있는 햄버거를 먹을 수 있다. 이 경우 다음과 같이 최대 5명의 사람이 햄버거를 먹을 수 있다.

• 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
• 4번 위치에 있는 사람: 5번 위치에 있는 햄버거
• 6번 위치에 있는 사람: 7번 위치에 있는 햄버거
• 9번 위치에 있는 사람: 8번 위치에 있는 햄버거
• 10번 위치에 있는 사람: 11번 위치에 있는 햄버거
• 12번 위치에 있는 사람: 먹을 수 있는 햄버거가 없음

 K=2인 경우에는 6명 모두가 햄버거를 먹을 수 있다.

• 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
• 4번 위치에 있는 사람: 3번 위치에 있는 햄버거
• 6번 위치에 있는 사람: 5번 위치에 있는 햄버거
• 9번 위치에 있는 사람: 7번 위치에 있는 햄버거
• 10번 위치에 있는 사람: 8번 위치에 있는 햄버거
• 12번 위치에 있는 사람: 11번 위치에 있는 햄버거

식탁의 길이 N, 햄버거를 선택할 수 있는 거리 K, 사람과 햄버거의 위치가 주어졌을 때, 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.

->

사람이라면 거리가 k인 구간을 모두 훑어서 가장 먼 거리에 있는 햄버거를 먹는다.

먹은 햄버거는 다른 사람이 다시 먹지 않도록 bool 배열로 방문처리를 해준다.

 

#include <iostream>
using namespace std;
int main(void){
    char arr[20000];
    bool visited[20000] = {false, }; //먹은 햄버거 표시
    
    int n,k;
    cin >> n >> k;
    for(int i = 0;i<n;i++){
        cin >> arr[i];
    }
    
    int cnt = 0;
    
    for(int i = 0;i<n;i++){
        if(arr[i] == 'P'){
            /*거리가 k인 구간을 모두 훑어서 햄버거이고, 먹지 않았다면 cnt 증가->*/
            
            for(int j = i-k;j<=i+k;j++){
                if(visited[j] == false && arr[j] == 'H'){
                    cnt++;
                    visited[j] = true;
                    break;
                }
            }
        }
    }
    cout << cnt;
}

 

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

2096번: 내려가기

#include <iostream>

//백준 2096 
/*기존의 하던 방식대로 2차원 dp테이블선언시 메모리 초과 -> n번만큼 갱신하면서 최대,최소 저장
*/

using namespace std;
int max(int a,int b){ //최대값 구하는 함수
    if(a>b){
        return a;
    }
    else{
        return b;
    }
}
 
int min(int a,int b){ //최소값 구하는 함수
    if(a<b){
        return a;
    }
    else{
        return b;
    }
}
int main(void){
    int arr[3]; //한 라인에 점수를 3개씩 입력받으면서 (왼쪽점수,중앙점수,오른쪽 점수)
    int max_dp[3]; //최대값을 갱신 할 DP 테이블
    int min_dp[3]; //최소값을 갱신 할 DP 테이블
    
    int n;
    cin >> n;
    
    for(int i = 0;i<n;i++){
        cin >> arr[0] >> arr[1] >> arr[2]; //점수를 한 줄씩 입력받고
        
         /*i가 0일때는 최대,최소 DP 테이블 모두 입력받은 값*/
        if(i == 0){ 
            max_dp[0] = arr[0];
            max_dp[1] = arr[1];
            max_dp[2] = arr[2];
            min_dp[0] = arr[0];
            min_dp[1] = arr[1];
            min_dp[2] = arr[2];
 
        }
        
        /*직전의 i-1번째의 최대 DP 테이블 정보 저장 */
        int past_max_one = max_dp[0]; 
        int past_max_two = max_dp[1];
        int past_max_three = max_dp[2];
 
        /*직전(i-1)번째 최소 DP 테이블 정보 저장 */
        int past_min_one = min_dp[0];
        int past_min_two = min_dp[1];
        int past_min_three = min_dp[2];
 
       
        /*그 외의 경우
        max_dp[0] -> 왼쪽 경로로 오는 경로 1) 직전의 왼쪽에서 내려오거나,
        2) 중앙에서 내려오는 경우
        의 최대 값
        
        max_dp[1] -> 중앙으로 오는 경로 1) 직전의 왼쪽에서 내려오거나, 2) 직전의 중앙에서 내려오거나,
        3) 직전의 오른쪽에서 내려오는 경우
        의 최대값
        
        max_dp[2] -> 오른쪽 경로로 내려오는 경우 1) 직전의 중앙에서 내려오거나,
        2) 직전의 오른쪽에서 내려오는 경우
        의 최대 값
        
        min도 마찬가지 */
        
         if(i != 0){
            max_dp[0] = max(past_max_one + arr[0],past_max_two + arr[0]);
            int big = max(past_max_one+arr[1],past_max_two+arr[1]);
            max_dp[1] = max(big,past_max_three + arr[1]);
            max_dp[2] = max(past_max_two + arr[2],past_max_three + arr[2]);
 
            min_dp[0] = min(past_min_one + arr[0],past_min_two + arr[0]);
            int small = min(past_min_one+arr[1],past_min_two+arr[1]);
            min_dp[1] = min(small,past_min_three + arr[1]);
            min_dp[2] = min(past_min_two + arr[2], past_min_three + arr[2]);
        }

    }
 
    cout << max(max(max_dp[0],max_dp[1]),max_dp[2]) << ' ';
    cout << min(min(min_dp[0],min_dp[1]),min_dp[2]);
 
}