Be a developer

기본적인 DP 문제이다. 임의의 한 지점(i 번째)에 있는 집이 빨강일 때, 초록일 때 파랑일 때로 나누어서 생각한다. 1)빨강일 때: min(i-1번 째 있는 집이 파랑, i-1번 째 있는 집이 노랑) + i번째가 빨강일 때 칠하는 비용 2)초록일 때: min(i-1번 째 있는 집이 빨강, i-1번 째 있는 집이 파랑) + i번째가 초록일 때 칠하는 비용 3)파랑일 때: min(i-1번 째 있는 집이 빨강, i-1번 째 있는 집이 초록) + i번째가 파랑일 때 칠하는 비용 따라서 DP 배열을 선언할 때 2차원 배열로 선언하고 dp[n][3]으로 생선한다.(n은 집의 개수, 3은 빨강,초록,파랑) 마지막 최솟값은 n번째 집의 min(빨강,초록,파랑) 이다. 코드는 아래와 같다. import java.io..

1. 중복체크를 할 때 list에 넣고 contains 메소드로 체크하는 것 보다 HashSet에 그냥 넣는 것이 속도가 훨씬 빠르다. HashSet은 별도의 정렬 작업이 없어서 Set 중에 가장 성능이 좋다고 한다. List는 본질적으로 순서도 같이 관리하기 때문에 시간이 오래 걸린다고 한다. 2. 정수형의 범위를 조심해라.(overflow가 나는 경우를 잘 살펴라) 오버플로우가 발생할 것 같으면 long으로 선언하자. 3. DFS를 돌 때 종료 조건에 return 을 넣는 것을 까먹지 말자! 4. Collections.sort 혹은 Arrays.sort로 String을 정렬할 때 String의 길이는 중요하지 않고, 알파벳 순서로만 정렬이 된다. 길이가 짧은 것이 앞에오게 해서 정렬하려면 Compar..

앞서 풀었던 숨바꼭질 문제처럼 최소 비용을 구하면 된다. 최소 비용으로 가는 방법의 수는 다이나믹 프로그래밍 기법을 이용한다. 즉, 만약 처음 방문하는 거면 최소 비용으로 도달한 것이기 때문에 바로 앞의 위치까지 가는 방법의 수를 그대로 넣어준다. 이미 방문했던 곳에 최소 비용으로 다시 도달하게 되면, 방법이 더 있는 것이므로 바로 앞의 위치까지 가는 방법의 수와 이전에 현재 위치까지 오는 최소 비용 방법의 횟수를 더해준다. 코드는 아래와 같다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include #include using namespace std; ..

한 번에 한 통을 붓기 때문에 가중치가 1이다. 또한 visit 배열을 만든다고 할 때 200*200*200 = 8000000이므로 시간안에 풀 수 있는 문제이다. bfs로 풀 수 있다. a에 들어 있는 물의 양이 0일 때는 queue에 다시 넣지 않고 답을 저장하는 vector에 넣을 것이고, 한 번 만들어진 경우는 visit 함수를 이용하여 다시 queue에 넣지 않을 것이므로 queue는 empty가 될 수밖에 없다. 푸는 방법은 어렵지 않지만, 경우의 수를 다 나누어 주는 것이 복잡하다. 코드는 아래와 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575..

한 번 연산할 때 출력할 문자열의 길이가 1증가 하므로 가중치가 1이라 할 수 있고, 필요한 최소 문자열의 길이를 구하는 것이므로 bfs로 풀 수 있다. 일단 string으로 문자열을 저장했더니 시간 초과가 났다. char로 저장해서 출력하자. 다음으로, 주석 친 부분처럼 l과 r연산을 했더니 틀렸다. 1000과 같이 0이 포함된 연산을 제대로 풀지 못해서 였다. 만약 처음 푼대로 l연산을 하면 16은 61이 된다. 하지만 16은 0016이므로 160이 되어야 한다. 덤벙대지 않고, 문제를 똑바로 보고 풀도록 하자! 따라서 코드는 아래와 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 ..

앞선 숨바꼭질 문제와 같다. 추가된 것이 있다면 답을 찾아가는 경로를 출력해야 한다. 그래서 경로를 저장하기 위한 배열 d를 하나 더 둔다. 도착지에서부터 출발지로 가면서 stack에 쌓은 후 pop하면서 출력한다. 물론 재귀 함수 호출을 통해서 출력해도 된다. 코드는 아래와 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #include #include #include using namespace std; int time..

최소 거리를 구하는 문제이고, 한 칸 이동하는 것이 가중치 1이므로 bfs로 풀 수 있다. 먼저 물이 퍼지는 데 걸리는 시간을 dist 배열에 저장하고, 고슴도치가 이동하는 것을 따로 visit 배열에 저장한다. 즉, bfs를 두 번 돌린다. 계속 틀렸다고 나오는 데 무슨 문제인지는 잘 모르겠지만, 조건을 걸러 내는 것이 매우 까다로운 문제인 것 같다. 조건을 통해 queue에 넣을 조건을 잘 거르는 것이 중요한 문제인 것 같다. 매우 짜증나게 시간 오래 잡아먹음 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 4..

최단 경로를 구하는 문제이고, 한 칸 이동하는 것을 가중치 1로 둘 수 있으므로 bfs로 풀 수 있는 문제다. 벽을 1번 부순 경우와 벽을 부수지 않은 상태로 이동하는 경우가 다르기 때문에 다른 정점으로 봐야 한다. 따라서 3차원 배열로 선언하여 벽을 부쉈을 때 비용과 부수지 않았을 때 비용을 구분하여 준다. 그리고 queue에는 벽을 부쉈는지 여부도 전달해주어야 한다. 처음에는 [row][col][0]에 비용을 저장하고, [row][col][1]에 벽을 부순 여부를 저장했는데, 이는 어느 특정한 칸을 왔을 때 벽을 한 번 부쉈는지 안 부쉈는지 경우의 수를 나누지 않은 것이었다. 아래는 처음 생각했던 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2..