카라멜마끼아또

개인 공부를 위한 공간입니다
상업적 용도로 활용되지 않습니다

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

조건

1. 지도의 숫자는 해당 칸의 높이

2. 시작 지점은 (0,0) 도착 지점은 (m, n)

3. 항상 내리막길만 이용 (이전 칸의 높이보다 낮은 칸으로만)

4. 상하좌우로만 이동

이 조건을 만족하는 경로의 개수를 모두 구하는 문제

"경로의 개수" 를 구해야 하기 때문에 dfs 를 사용

재귀를 통한 깊이 우선 탐색으로 조건에 나온 현재 지점보다 낮은 경로 탐색

public class Main {
    
    static int m, n;
    static int dm[] = {1, 0, -1, 0};
    static int dn[] = {0, 1, 0, -1};
    static int dp[][];
    static int input[][];
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(reader.readLine());

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        input = new int[501][501];
        dp = new int[501][501];
        for(int i=0; i<m; i++){
            st = new StringTokenizer(reader.readLine());
            int idx = 0;
            while(st.hasMoreTokens()){
                input[i][idx] = Integer.parseInt(st.nextToken());
                dp[i][idx++] = -1;
            }
        }

        int result = dfs(0,0);

        System.out.println(result);
    }
    
    
    public static int dfs(int x, int y){
        
        if(x==m-1 || y==n-1){
            return 1;
        }

    
        if(dp[x][y] != -1){
            return dp[x][y];
        }

        dp[x][y]=0;

        for(int i=0; i<4; i++){
            int nextX = x+dm[i];
            int nextY = y+dn[i];

            if(nextX >= 0 && nextY >= 0 && nextX <m && nextY < n && input[nextX][nextY] < input[x][y]){
                dp[x][y] += dfs(nextX, nextY);
            }
        }


        return dp[x][y];
    }
}

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

T는 상담에 소요되는 시간

P 는 상담을 통해 받는 돈

조건

1. 상담은 동시에 하나

2. n+1 일부터는 이미 퇴사한 상태이기 때문에 상담 진행이 불가능

3. 상담이 끝난 후 돈을 받음 (다음날)

상향식으로 풀이

# 1일차

n=1

dp[1] = 0

1일차에는 어떤 상담도 완료되지 않았기 때문

1일차 이후 상담 가능한 날짜

int nextDay = 1 + t[1]

1일차 상담에는 3일이 소요되므로 nextDay = 1 + 3 = 4

dp[4] = max(dp[4], dp[1]+p[1])

dp[4] = (4일에 받을 수 있는 최대 금액) = (1일차 상담 3일치를 끝내고 받은 금액) = 10

# 2일차

n=2

dp[2] = 0

2일차 상담에는 5일 소요

nextDay = 2 + 5 = 7

dp[7] = max(dp[7], dp[2]+p[2])

dp[7] = 20

.....

# n일차

dp[n]=0

n일차 상담에는 t[n] 일 소요

nextDay = n + t[n]

dp[nextDay] = max(dp[nextDay], dp[n] + p[n])

** 주의

n번째 날의 상담 소요시간이 1일이라면, n+1 일에 금액을 받을 수 있으므로 dp 배열을 n+2 로 초기화

>> 1일 ~ n+1 일 까지

    public void solution15486() throws Exception{

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());

        int t[] = new int[n+2];
        int p[] = new int[n+2];
        int dp[] = new int[n+2];

        for(int i=1; i<=n; i++){
            String[] temp = reader.readLine().split(" ");
            t[i] = Integer.parseInt(temp[0]);
            p[i] = Integer.parseInt(temp[1]);
        }
        int max = -1;

        for(int i=1; i<=n+1; i++) {
            if(max < dp[i]){
                max = dp[i];
            }
            int nextDay = i+t[i];
            if(nextDay < n+2){
                dp[nextDay] = Math.max(dp[nextDay], max+p[i]);
            }
        }
        System.out.println(dp[n+1]);
    }

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

풀이

# 2x1

2x1 1개

1가지 경우의 수

# 2x2

2x1 2개

1x2 2개

2가지 경우의 수

# 2x3

3가지 경우의 수

# 2x4

5가지 경우의 수

......

점화식

dp[n] = dp[n-2] + dp[n-1] 도출 가능

    public void solution11726() throws Exception{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());

        int dp[] = new int[1001];


        dp[1]=1;
        dp[2]=2;

        for(int i=3; i<=n; i++){
            dp[i] = (dp[i-1]+dp[i-2])%10007;
        }

        System.out.println(dp[n]);

    }

여기서 주의할 점 !!

dp 배열 크기를 n+1 로 잡으면 런타임 에러 (ArrayIndexOutOfBounds) 발생하기 때문에

입력의 최대값인 1000 + 1 의 길이로 최대 배열 생성 후 사용

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

풀이

경우의 수를 따져 보면

# 1

1

1개 

# 2

1+1

2

2개

# 3

1+1+1

2+1

1+2

3

4개

# 4

1+3

1+1+2

2+2

1+1+1+1

2+1+1

1+2+1

3+1

7개

4의 경우를 자세히 살펴보면

1+3

1+1+2

2+2

1+1+1+1

2+1+1

1+2+1

3+1

즉

1번째 케이스들에 +3

2번째 케이스들에 +2

3번째 케이스들에 +1

을 해준것과 동일

dp[n] = dp[n-3] + dp[n-2] + dp[n-1]

이라는 점화식 도출

    public void solution9095() throws Exception{

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());
        int input[] = new int[n];
        int dp[] = new int[12];
        for(int i=0; i<n; i++)
            input[i] = Integer.parseInt(reader.readLine());

        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for(int i=4; i<=11; i++)
            dp[i] = dp[i-3]+dp[i-2]+dp[i-1];

        for(int i : input)
            System.out.println(dp[i]);
    }

경우의 수를 구하고자 하는 숫자의 최대값이 11이기 때문에 dp 배열의 길이를 12로 선언

dp[1] ~ dp[3] 까진 1, 2, 4 의 값을 넣어주고

4번째 케이스부터 앞선 3개의 값을 더해서 값 저장

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

풀이

문제에 나타난 조건 2개

1. 계단은 한 번에 1칸 혹은 2칸 이동 가능

2. 3칸 연속으로 밟기 불가능

2개의 조건을 만족하며 N 번째 계단을 밟기 위해서

1. N-3 을 밟고 N-2 를 건너 뛰고 N-1, N 밟기

2..N-2 를 밟고 N-1 을 건너뛰고 N 밟기

이렇게 두 가지 경우가 존재 >> 연속 3개의 계단은 못밟기 때문

따라서 위 2가지의 값 중 큰 값 + N 번째 계단의 점수를 더한 값이 N 번째 계단의 점수 최대값

각 계단의 점수를 저장하고 있는 input 배열

N번째 계단의 최대점수를 기록하는 dp

dp[N] = Max(dp[N-2], dp[N-3]+input[N-1]) + input[N]

라는 점화식 도출

    public void solution2579() throws Exception{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());


        int input[] = new int[n+1];
        int dp[] = new int[n+1];

        for(int i = 1; i<=n; i++)
            input[i] = Integer.parseInt(reader.readLine());

        dp[1] = input[1];

        if(n>=2)
            dp[2] = input[1] + input[2];


        for(int i=3; i<=n; i++)
            dp[i] = Math.max(dp[i-2], dp[i-3]+input[i-1])+input[i];

        System.out.println(dp[n]);
    }

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

풀이

이 문제같은 경우는 Time out에 집중

직관적인 로직으로 n만큼 입력받는대로 sort 하고 중간값 출력 >> 당연하게도 시간초과

시간초과 해결하기 위해서 for문으로 sort를 반복하는 방법 대신 priority queue를 사용해서 중간값을 도출

두 개의 priority queue 사용

하나는 최대힙

하나는 최소힙

왜?

그래야 내용물을 끄집어 내지 않고도 중간값 도출이 가능하니까

1. 두 우선순위 큐의 사이즈를 비교해서 같으면 최대힙에 삽입, 다르면 최소힙에 삽입

>> 입력값 개수가 짝수일 경우 작은 쪽을 중간값으로 출력해야 하기 때문에

2. 두 큐에서 우선순위가 가장 높은 원소의 값을 비교

 내림차순(최대힙) 쪽의 크기가 크면 두 값을 swap

3. 내림차순(최대힙) 에서 가장 높은 우선순위의 값을 결과 string에 저장

4. 결과값 출력

좀 더 자세하게 설명해보면

초기

[ ] [ ]

1 입력 

[1] [ ]

:: 두 큐의 사이즈가 동일하기 때문에 maxPq에 삽입

중간값 1

5 입력

[1] [5]

:: 두 큐의 사이즈가 다르기 때문에 minPq에 삽입

:: swap 안함

중간값 1

2 입력

[1 2] [5]

:: 두 큐의 사이즈가 동일하기 때문에 maxPq에 삽입

:: swap 안함

중간값 2

10 입력

[1 2] [5 10]

중간값 2

-99 입력

[-99 1 2] [5 10]

중간값 2

7 입력

[-99 1 2] [5 7 10]

중간값 2

5 입력

[-99 1 2 5] [5 7 10]

중간값 5

>> 결과값 1 1 2 2 2 2 5

** 문제에 나와있는 케이스에서는 swap의 필요성을 못느껴서 임의의 케이스를 써보면

10 입력

[10] [ ]

중간값 10

5 입력

[10] [5]

:: 여기서 maxPq.peek() > minPq.peek() 조건이 만족하기 때문에 두 값을 swap

[5] [10]

중간값 5

1입력

[1 5] [10]

중간값 5

3 입력

[1 5] [3 10]

:: 조건 만족하므로 swap

[1 3] [5 10]

중간값 3

>> 결과값 10 5 5 3

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        StringBuilder sb = new StringBuilder();

        PriorityQueue<Integer> maxPq = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> minPq = new PriorityQueue<>();


        for(int i=0; i<n; i++){

            int k = Integer.parseInt(reader.readLine());

            if(maxPq.size() > minPq.size()){
                minPq.add(k);
            }
            else{
                maxPq.add(k);
            }

            if(maxPq.size()>0 && minPq.size()>0){
                if( maxPq.peek() > minPq.peek()){
                    int temp=maxPq.poll();
                    maxPq.add(minPq.poll());
                    minPq.add(temp);
                }
            }
            sb.append(maxPq.peek()+"\n");

        }
        System.out.println(sb);

https://level.goorm.io/exam/163680/%EC%A7%81%EC%82%AC%EA%B0%81%ED%98%95-%EB%A7%8C%EB%93%A4%EA%B8%B0/quiz/1

풀이

그리디 알고리즘 활용

1. 직사각형을 만들기 위해서 필요한 막대는 4개

2. 같은 길이의 막대 2개를 한 세트로, 두 세트가 필요

3. 같은 길이의 막대가 4개 이상이면 정사각형 만들기 가능

!! 길이가 긴 막대부터 차례로 직사각형을 만들어 나가는 것이 만들 수 있는 직사각형 넓이의 합의 최대값 !!

처음엔 map에 key값에 막대 길이, value값에 막대 개수를 저장하고 iterator로 탐색하며 사각형을 구현하도록 코드를 작성했는데, Time out 발생

>> 

입력값의 최대 크기인 10의 6승만큼 크기를 가진 input 배열을 선언하고 해당 배열의 인덱스를 막대기의 길이로, 인덱스의 값을 막대기의 개수로 대입하여 사용

** input 배열을 전역변수로 선언하여 Time out 방지

input 배열 뒤부터 길이가 긴 순으로 탐색

막대가 2개 이상이라면 킵하고

그 이후에 2개 이상 막대가 발견되면 이전의 막대와 직사각형을 만들어 넓이 계산 후 answer에 더함

-- 반복

long long input[1000000] = { 0, };	// 막대 길이와 막대 개수 정보를 담을 배열 전역변수 선언
// index : 막대 길이
// input[index] : index 길이의 막대 개수
	int main() {

		int n;	// 입력값
		cin >> n;

		long long answer = 0;
		bool flag = true;	// 개수가 2 이상인 막대가 선택됬을 때, 이전에 이미 선택 된 막대가 있는지 판단하는 변수

		int curVal = 0;

		// 반복문으로 input에 막대 개수 정보 입력
		for (int i = 0; i < n; i++) {
			int temp;
			cin >> temp;
			input[temp]++;
		}
		
        // 길이가 긴 순으로 탐색
		for (long long i = 1000000; i > 0; i--) {
			// 만약 막대의 개수가 2개 이상이고
			if (input[i] >= 2) {
				// 이전에 선택된 막대가 없다면
            			if (flag) {
					curVal = i;	// curVal에 막대의 길이 저장
					flag = false;
				}
                // 이전에 선택된 막대가 있다면
				else {
					answer = answer+ (curVal * i);	// 이전에 선택된 막대와 현재 막대를 곱해서 넓이 계산
					flag = true;
				}
				input[i] -= 2;	// 막대의 개수 2개 감소
				i++;	// 예를 들어 현재 막대가 4개일 경우 같은 길이의 막대를 4개 사용하여 사각형을 만들 수 있기 때문에 현재 막대를 한 번 더 탐색하기 위한 i값 1 증가
			}
		}
		cout << answer << endl;
	}

https://level.goorm.io/exam/49096/%EC%96%B4%EB%B6%80%EC%9D%98-%EA%B3%A0%EA%B8%B0%EC%9E%A1%EC%9D%B4/quiz/1

풀이

투포인터 알고리즘

start와 end 변수를 각각 시작, 끝 포인터로 활용

1. input[start] 부터 input[end]  까지 더한 값 sum이 m보다 작으면 end+ 1

2. m보다 크면 start + 1

3. m과 같으면 answer + 1 (경우의 수 카운트)

4. m보다 작으면서 end 포인터가 input의 길이를 벗어날 경우 >> 더이상 정답이 나올 수 없는 경우

	int main() {

		int n;
		int m;
		cin >> n >> m;

		vector<int> input;

		// input vector에 입력 값 저장
		for (int i = 0; i < n; i++) {

			int temp;
			cin >> temp;
			input.push_back(temp);
		}

		int start=0;		// 왼쪽 포인터
		int end=0;			// 오른쪽 포인터
		int answer = 0;		// 정답 카운트

		// end가 input 의 범위 안일 경우 반복
		while (end<n) {

			// start ~ end 의 합
			int sum=0;
			for (int i = start; i <= end; i++)
				sum += input[i];
			
			// sum == m 일 경우 정답 카운트 + 1
			if (sum == m) {
				answer++;
                
                // start 포인터 1 증가
				start += 1;
			}

			// sum < m 일 경우
			else if (sum < m)
            	// 다른 수를 더해서 m을 만들어야 하므로 end 포인터 증가
				end += 1;
                
            // sum > m 일 경우
			else if (sum > m)
            	// 수를 작게 만들어야 하므로 start 포인터 증가
				start += 1;
		}
		cout << answer << endl;
	}

https://level.goorm.io/exam/167345/%EB%8B%A8%ED%92%8D%EB%82%98%EB%AC%B4/quiz/1

풀이

처음엔 단순하게 타일 하나하나 탐색하면서 인접타일의 값이 0이라면 현재 타일의 값을 -1 해봤는데

하루 단위에서 인접한 타일의 값이 1에서 0으로 바뀐 경우 해당 타일을 0으로 인식하여 값이 변동되는 문제 발생

-- 큐에 좌표값을 담아서 따로 한번에 값 변경하는 방식으로 해결

1. 모든 타일을 탐색

2. 0이 아닌 타일 발견 시, 해당 타일의 4방향으로 인접한 타일들의 값이 0이라면, 해당 타일의 x, y 좌표를 큐에 삽입

3. 큐에서 하나하나 꺼내면서 해당 타일의 값을 -1, 0보다 작아진다면 0으로

4. answer 변수 +1 (하루가 지남)

-- 반복

queue<pair<int, int>> inputSearch(vector<vector<int>> input, int n) {
	
    // input vector 값을 update하기 위한 좌표 정보를 담을 큐
	queue<pair<int, int>> q;
	int xdir[4] = { 0, 0, 1, -1 };	// 인접노드 탐색 x방향
	int ydir[4] = { 1, -1, 0, 0 };	// 인접노드 탐색 y방향

	// 모든 타일 하나하나 방문하며
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int curX = i;
			int curY = j;

			// 현재 타일이 0이 아니라면 (물들 수 있다면)
			if (input[curX][curY] != 0) {
				// 현재 타일과 인접한 4개의 타일 탐색
				for (int k = 0; k < 4; k++) {
					int nextX = curX + xdir[k];
					int nextY = curY + ydir[k];

					// 인접한 타일이 전체 범위 안이면서
					if (nextX >= 0 && nextY >= 0 && nextX < n && nextY < n) {
						// 인접한 타일의 값이 0이라면 q에 삽입
                        if (input[nextX][nextY] == 0) {
							q.push(make_pair(curX, curY));
						}
					}
				}
			}
		}

	}

	// 인접한 타일의 영향을 받아 물들어갈 타일의 좌표를 담은 큐를 return
	return q;
}


vector<vector<int>> inputUpdate(queue<pair<int, int>> q, vector<vector<int>> input) {

	// 큐 안의 좌표를 하나하나 꺼내면서 값을 -1
	while (!q.empty()) {

		int x = q.front().first;
		int y = q.front().second;

		q.pop();
		input[x][y] -= 1;

		if (input[x][y] < 0)
			input[x][y] = 0;
	}
	
    // 변경된 input vector를 return
	return input;
}


int main() {

	int n;		// x, y축 크기
	cin >> n;

	vector<vector<int>> input;		// input 값을 담을 vector 컨테이너

	int answer = 0;
    
    // 반복문으로 input vector에 문제 입력값 삽입
	for (int i = 0; i < n; i++) {
		vector<int> temp;
		for (int j = 0; j < n; j++) {
			int m;
			cin >> m;
			temp.push_back(m);
		}
		input.push_back(temp);
	}

	// while 한 번이 하루
	while (1) {

		queue<pair<int, int>> q = inputSearch(input, n);

		// q에 아무것도 담겨있지 않다면 >> 더이상 물들 단풍나무가 없다면 while 탈출
		if (q.empty())
			break;

		// q에 값이 있다면 하루가 지나고
		answer++;
        
        // input vector의 값을 변경 (물든 상태로)
		input = inputUpdate(q, input);

	}


	cout << answer << endl;

}

https://level.goorm.io/exam/167337/%EB%92%A4%ED%86%B5%EC%88%98%EA%B0%80-%EB%94%B0%EA%B0%80%EC%9B%8C/quiz/1

풀이

스택을 이용하는 문제

문제에 나와있는

** A 산봉우리에서 B산봉우리를 보기 위한 조건?

1. A가 B보다 왼쪽에 있어야 하고 (A < B)

2. A와 B 사이에 있는 모든 산봉우리가 A보다 작아야 한다

라는 조건을 활용

산봉우리를 왼쪽부터 순서대로 선택

스택의 top을 살펴보고, 현재 선택된 산봉우리보다 작으면 pop

>> 왜? 현재 선택된 산봉우리보다 작은 산봉우리는 현재 선택된 산봉우리를 포함하여 오른쪽에 있는 모든 산봉우리도 볼 수 없기 때문에

현재의 값을 push 하면 스택의 크기가 선택된 산봉우리를 볼 수 있는 산봉우리의 개수가 됨

int main() {

	int n;	// 산봉우리 개수
	cin >> n;

	stack<int> s;
	vector<int> answer;		// 정답을 담을 vector

	answer.push_back(0);	// 제일 왼쪽 산봉우리는 바라보는 신선이 없으므로 항상 0

	for (int i = 1; i < n; i++) {
		int input;		// 산봉우리의 높이 입력
		cin >> input;
		
        // 스택이 비어있지 않고, top() 보다 input의 값이 크거나 같다면
		while (!s.empty() && s.top() <= input)
			s.pop();	// 스택의 값을 pop
		
        // 그 후 스택에 현재 input을 push
		s.push(input);
        
        // 스택의 size를 answer vector에 저장
		answer.push_back(s.size());

	}

	// 정답 출력
	for (auto a : answer)
		cout << a << " ";
	
	return 0;

}