mintuchel mintuchel

이 문제를 처음 봤을때 dp로 풀어야겠다 생각함 이유는 아래와 같다 1. 높은 점수부터 쌓는다고 최댓값이 되는게 아니다 2. 그렇다고 마감 빠른 것부터 쌓는다고 최댓값이 되는게 아니다 즉 특정 명제를 참으로 두고 매 순간 선택했을시 답이 나오는게 아니기 때문이다. 그래서 모든 경우의 수를 해보는 dp가 맞다고 생각함 배낭문제처럼 접근함 1번째 과제 했을 경우 최댓값 1~2번째까지 했을 경우 최댓값 1~3번째까지 했을 경우 최댓값 근데 여기서 중요한게 마감일 순으로 정렬하고 해야함 그래야 2차원 dp가 맞게 나온다 dp[i][k] : i 과제까지 넣었을때 k일까지 할 수 있는 최댓값 dp[i-1][k] : i-1 번째 과제까지 넣었을때 k일까지 할 수 있는 최댓값 dp[i-1][k-1] : i-1 번째 과..

그리디 문제인건 알았고 우선 처음에는 deque로 풀었음 앞 뒤 중 빠른거부터 붙여나가는 식으로 근데 앞뒤가 같을때가 문제임 앞뒤가 같으면 다른 문자가 나올때까지 탐색해야함 그래서 어디서 빠른게 나오는지 확인하고 그쪽부터 빼야함 이게 check함수임 그래서 배열탐색이 필요해서 그냥 deque를 arraylist로 바꿔서 품 import java.io.*; import java.util.*; public class Main { static List arr = new ArrayList(); public static boolean check(int front, int rear){ while(front

한 문자열에서 특정 문자가 띄워져 있으면 안된다는 얘기 그래서 visited 로 방문여부를 확인만 해주면 된다 근데 예외가 있다 중복되서 나올때는 띄워져있는게 아니므로 skip해주면 된다 즉 전꺼랑 다를때만 visited 여부를 체크해주면 됨 3분만에 짠거 같다 #include #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N; cin >> N; string str; bitset visited; int flag, cnt=0; for (int i = 0; i > str; visited.reset(); visited[s..

처음 문제를 봤을때는 그리디 문제인줄 하지만 예제를 보면 그리디로 풀면 안된다는걸 알 수 있다 무조건 3으로 나누는게 좋고 1로 나누는게 제일 안좋다는 생각이 먼저 드는데 10을 보면 10 - 9 - 3 - 1 로 3번만에 걸쳐서 할 수 있는걸 그리디로 풀면 10 - 5 - 4 - 2 - 1 이렇게 4번 걸린다 그래서 dp로 풀어야한다 이건 자바 연습겸 자바로 품 import java.io.*; public class Main { public static void main(String[] args) throws IOException { int[] dp = new int[1000001]; BufferedReader br = new BufferedReader(new InputStreamReader(Syste..

우선 이 문제는 굉장히 중요한 문제다. 최단거리 문제로 dijkstra 랑 floydwarshall을 이용해서 풀 수 있는데 둘 다 시간초과 나지 않고 풀 수 있다. 그리고 floydwarshall로 풀때는 일반적인 floydwarshall 써서 그대로 풀어주면 되는데 dijkstra는 살짝 새로운 접근방식으로 풀어야한다 일단 내 첫번째 풀이인 floydwarshall 부터 보고 내가 게시판을 보고 깨달은 dijkstra 풀이법도 보자 [1. floydwarshall solution] 우선 두 가지를 파악할 수 있다 1. X 마을로 오고 가야함 2. 최단거리로 오고 가야함 이러면 최단거리 알고리즘인 다익스트라 벨만포드 플로이드 워셜 중 하나를 택하면 됨 ㅇㅇ 근데 시간이 무조건 양수이므로 일단 벨만포드를..

얘도 dp문제임 01 배낭문제인 평범한 배낭 이 문제랑 똑같은 상황임 얘도 가치있는거부터 넣는다고 좋은게 절대 아님 greedy로 안풀림 greedy로 풀었을때의 반례를 보자면 총 10 담을 수 있는데 8 8 5 5 4 4 이렇게 있으면 5 4 조합 넣는게 훨씬 이득임 하지만 greedy로 풀면 8에서 끝남 그래서 dp로 풀어야함 greedy가 안먹히기 때문 #include #define SIZE 21 using namespace std; int N; int L[SIZE], J[SIZE]; int dp[SIZE][101]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; for (int i = 1; i > L[i]; // ..

우선 처음에는 방문여부를 visited를 통해 파악하려고 했다 bitset으로 방문여부를 놓고 비트연산을 통해 특정 물건을 포함한 결과인지 아닌지를 통해 포함여부를 파악하려고 함 근데 2차원 배열로 dp를 만들면 포함여부를 확인하지 않아도 됨 [2차원 dp배열] dp[i][k]에서 i번째 줄인 dp[i]는 지금까지 나온 최적의 상황에서 i번째 물건을 포함시키면 어케 바뀔까? 를 보는거임 즉 2차원 배열로 만듦으로써 visited 변수 사용하고 방문여부를 계산하지 않아도 됨 이렇게 나뉘는거임 1. i번째 이전 i번째 이전 물건들 조합으로 즉 1번부터 i-1번 물건 가지고 나올 수 있는 각 kg마다 최고의 value값 2. i번째 1번부터 i-1번 물건 가지고 나올 수 있는 최적의 조합결과에, 즉 지금까지 ..

이 문제때문에 짜증이 나지는 않았다. 시간초과가 계속 나는데 (사실 날 수 밖에 없었다. 날거라는 것도 안상태에서 반포기 반기대상태로 품) 정답을 보니 이건 틀릴만 했다. 아니 틀려야만 한다 왜? 내가 난생 처음보는 접근법이었기 때문. 무슨 알고리즘 이름이 있는것도 아니다. 그냥 새로운 접근법인데 알아놓으면 좋을듯 일단 이진검색트리는 아래와 같이 만들어진다. 이진검색트리는 완전이진트리가 아니다. 그냥 이진트리이다. 무조건 완전일 필요가 없다 근데 이 트리를 list 즉 vector로 표현할 수 있다 옆으로 늘리고 튀어나온 것들을 눌러줘서 말이다 즉 트리를 정렬된 리스트로 표현할 수 있다는거임 이건 이진검색트리를 전위순회하면 오름차순으로 나오는 걸 생각해보면 이해가 된다 그래서 이렇게 트리를 리스트로 표현..

제한이 있는 dp는 dp를 점화식으로 계산할때 if로 조건에 맞게 dp값을 찾아주려고 하면 안된다 이 문제는 3개의 계단을 연속으로 오르면 안된다는 조건을 가지고 있는데 이걸 현재 3개를 연속으로 올랐을때랑 안올랐을때를 if문에 넣어서 각 dp값을 구하려고 하면 안됨 그냥 3개 올라갈 수 없다는걸 납득하고 이에 맞는 점화식을 구해주면 됨 dp[0] dp[1] dp[2] 는 이미 값이 정해져 있으므로 dp 돌기전에 미리 초기화 해주고 3부터 계산해주면 됨 #include #define SIZE 301 using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int stairs[SIZE] = { 0, }, dp[SI..

조합 문제인데 이 nCr을 n-1Cr-1 + n-1Cr 을 이용해서 dp로 미리 다 구한다음에 답만 출력해주면 됨 dp로 미리 모든 nCr을 다 구해놓는 생각을 일단 해야하고 dp의 의의가 뭐냐 memorization 즉 한번 계산한건 다시는 계산하지 않는거임 그래서 n-1Cr-1과 n-1Cr은 이미 계산된 값 즉 dp 2차원 배열 값을 재사용해주면 된다 #include #define SIZE 30 using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int dp[SIZE][SIZE]; for (int n = 1; n < 30; n++) dp[n][1] = n; for (int n = 1; n < 30; n+..