14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 다이나믹 프로그래밍? 혹은 브루트포스 ? 문제이다. 일단 1일차부터 N일차까지 각 상담을 첫 상담으로 한다고 하면, i일차 상담 + ( [i일차 상담이 끝나는 날짜~N일차 상담] 중에서 가장 이득이 큰 상담)이 해당 일차의 가장 이득이 높은 상담이 될 것이다. 그러면 또 i일차 상담이 끝나는 날짜 ~ N일차 상담 중에서 가장 이득이 큰 상담을 구하려면, 해당 일자를 j 일로 놓고 j일차 상담 + ( [ j일차 상담이 끝나는 날짜~ N일차 상담 ] 중에서 가장 이득이 큰 상담) 을 구하면 된다. 그러면 이걸 1일차부터 N일차까지 모두 구하면 되는 것이다. 이걸 더 완벽한 DP로 풀기위해서는 bottom..
17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 문제 설명에 나온대로 구현하면 되는 시뮬레이션 문제이다. 확산: 4방향으로, 모든 미세먼지가 동시에 확산된다. 정화: 공기청정기의 윗부분과 아랫부분의 바람의 방향에 따라서 미세먼지의 자리가 옮겨진다. 로직은 아래와 같다. BFS로 4방향 확산을 시켜준다. 여기서 확산시킨 미세먼지의 값은 변경해주되, 확산 된 미세먼지의 값은 다른 배열에 같은 위치에 저장(플러스) 해둔다. 모든 위치의 미세먼지의 확산이 끝났다면, 저장해둔 확산된 미세먼지를 각 위치에 더해준다. 공..
1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 그리디 문제이다. 일단 식에서 최소값이 되게하려면 마이너스 부호가 나온 곳부터 다음 마이너스 부호가 나올 곳까지 괄호를 쳐주면 된다. 이를 이용해서 문제를 풀어보면, 일단 식의 첫번째 문자는 무조건 숫자이므로, 숫자를 읽어서 sum에다 저장해준다 두번째 문자부터 읽는데, 해당 문자가 마이너스이면, 괄호를 쳐서 괄호 안에 해당하는 모든 숫자의 합을 현재 sum에다가 빼준다. 만약 해당 문자가 플러스이면, 역시나 마이너스부호가 나올때까지 모두 더해서 sum에다..
16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모�� www.acmicpc.net 삼성역테에 나온 문제답게 시뮬레이션+bfs였고 디버깅이 오래걸렸다. 그래도 조건만 잘 숙지하면 그렇게 어려운 문제는 아니었다. (근데 난 이 조건을 처음에 잘못봐가지고 디버깅하는데 오래걸림 ^^;;) 일단 나의 풀이는 아래와 같다 bfs 돌기전에, 미리 국경이 열릴 나라들(1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100) 을 모두 체크해준다 -> 여기서 체크된 나라가 0 이면 인구이동 끝. 체크된 나라 && visited가 false인 나라만 ..