백준 11501, 2169, 프로그래머스 체육복

📈 백준 11501 : 주식  

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

11501번: 주식

 

📈 메인 로직

• 각 날짜의 주식가격을 배열에 쭉 저장해둔다. 
• 그리디 유형의 문제긴 하지만, 무조건 높을때 다 팔고 끝나는것이 아니라 마지막날에도 이전보다 올랐다면 팔 수 있다.
• 뒤에서부터 차례로 돌면서 현재 내가 가진 최댓값보다 높은 가격이 나왔다 =  그날 기점으로 가격이 떨어졌다 이것이므로 최댓값을 갱신해준다.
• 그 외에는 최댓값보다 낮은 날이므로 무조건 사뒀다가 파는게 이득이라 answer에 더해준다. 

📈 메인 로직을 코드화하면 아래와 같다. 

int temp = price[days-1];
for (int d = days-2; d >= 0; d--) {
	if (temp < price[d]) {
		temp = price[d]; // 최댓값 갱신해준다. 
	} else {
		answer += (temp - price[d]); // 더 낮은값일때는 계속 사놓는 것이 이득
	}
}

 

📈 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class p11501 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            int days = Integer.parseInt(br.readLine());
            int[] price = new int[days];
            int answer = 0;
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int d = 0; d < days; d++) {
                price[d] = Integer.parseInt(st.nextToken());
            }

            int temp = price[days-1];
            for (int d = days-2; d >= 0; d--) {
                if (temp < price[d]) {
                    temp = price[d];
                } else {
                    answer += (temp - price[d]);
                }
            }

            System.out.println(answer);

        }

    }
}

 

 

 

---

 

 

🤖 백준 2169 : 로봇 조종하기

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

2169번: 로봇 조종하기

 

 

 

🤖 문제 유형 찾기 : DP

• 문제 조건을 보면 이러한 말들이 있다. 
  • 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 한다.
  • 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오.
• 처음에는 2차원 배열, 3방향으로 움직일 수 있다는 조건을 보고 BFS를 생각했는데, BFS는 최단거리 찾는것이므로 가치의 합이 최대가 되는 것이라면..하고 DFS를 생각했었다.
• 하지만 제한시간이 1초이고 n,m이 1000까지 갈 수 있으므로 동적계획법으로 푸는 건가? 라는 생각을 했다. (위의 조건을 보고 / 그리고 실제로 DP문제였다. )

🤖 메인 로직 

 

• 이동 가능한 방향은 좌, 우, 하 이렇게 3가지이고, DP[ i ][ j ]에서 위, 오른쪽, 왼쪽을 다 비교해보고 Max를 찾아야 한다.
• 위로 돌아가는 것은 불가능하므로, 무조건 DP 2차원 배열의 맨 윗줄은 map에서 가져와야 한다.

DP[0][0] = map[0][0];
for (int j = 1; j < col; j++) {
	DP[0][j] = DP[0][j-1] + map[0][j];
}

 

• 각 칸 별로 왼쪽에서 탐색해서 오는 경우와 오른쪽에서 탐색해서 오는 경우 중 더 큰 걸 찾아야 한다.

// 왼쪽에서 출발
left[0] = DP[i-1][0] + map[i][0];
for (int j = 1; j < col; j++) {
	left[j] = Math.max(DP[i-1][j], left[j-1]) + map[i][j];
}

// 오른쪽에서 출발
right[col-1] = DP[i-1][col-1] + map[i][col-1];
for (int j = col-2; j >= 0; j--) {
	right[j] = Math.max(DP[i-1][j], right[j+1]) + map[i][j];
}

 

• 왼쪽 오른쪽 다 탐색 후 MAX로 갱신해준다. 

for (int j = 0; j < col; j++) {
	DP[i][j] = Math.max(left[j], right[j]);
}

 

 

🤖 전체코드 

import java.util.*;
import java.io.*;
public class p2169 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int row = Integer.parseInt(st.nextToken());
        int col = Integer.parseInt(st.nextToken());

        int[][] map = new int[row][col];
        int[][] DP = new int[row][col];

        for (int i = 0; i < row; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < col; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        DP[0][0] = map[0][0];
        for (int j = 1; j < col; j++) {
            DP[0][j] = DP[0][j-1] + map[0][j];
        }

        for (int i = 1; i < row; i++) {
            int[] left = new int[col];
            int[] right = new int[col];

            // 왼쪽에서 출발
            left[0] = DP[i-1][0] + map[i][0];
            for (int j = 1; j < col; j++) {
                left[j] = Math.max(DP[i-1][j], left[j-1]) + map[i][j];
            }

            // 오른쪽에서 출발
            right[col-1] = DP[i-1][col-1] + map[i][col-1];
            for (int j = col-2; j >= 0; j--) {
                right[j] = Math.max(DP[i-1][j], right[j+1]) + map[i][j];
            }
            for (int j = 0; j < col; j++) {
                DP[i][j] = Math.max(left[j], right[j]);
            }
        }

        System.out.println(DP[row-1][col-1]);
    }


}

 

 

 

 

---

 

 

 

⛹🏻‍♀️ 프로그래머스 : 체육복 

https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스

 

 

⛹🏻‍♀️ 메인로직

• 먼저 모든 학생들이 참석할 수 있다고 가정하고 answer을 초기화 시킨 다음, 참석 불가능한 애들만 빼주면 된다.
• set에다가 여벌을 가지고 온 학생들 번호를 넣는다.
• 문제 조건에 따르면, 여벌 가지고 온 애들이 도난당한 경우 여벌을 빌려줄 수 없다. 그러므로 먼저 이 경우를 반복문을 돌린다.
  • reserve 배열 탐색하면서 set과 동일한 애가 있는 경우가 위의 예시이므로, set에서 제거해준 후 list에 넣지 않는다. 
• list는 중복을 제거한, 진짜 잃어버린 애들을 담는 리스트이며, 번호 순대로 정렬해준다.(체격 순으로 번호가 매겨지니까) 
• 그 후 set에서 자기 앞뒤 사이즈의 여벌이 있는지 확인하고, 없다면 answer--해준다. 

⛹🏻‍♀️ 전체코드 

import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n;
        Set<Integer> set = new HashSet<>();
        List<Integer> list = new ArrayList<>();
        for (int i : reserve) {
            set.add(i);
        }
        for (int i : lost) {
            if (set.contains(i)) {
                set.remove(i);
            } else {
                list.add(i);
            }
        }
        Collections.sort(list);
        
        for (int i : list) {
            if (set.contains(i-1)) {
                set.remove(i-1);
            } else if (set.contains(i+1)) {
                set.remove(i+1);
            } else {
                answer--;
            }
        }
        return answer;
    }
}