나 요리학원 출신임

다이어트를 하기위해 최적의 햄버거를 찾는 최고의 문제다 실생활에서 우리가 마주칠수있는 현실적인 문제 굿 일단 이 문제는 DP를 이용해서 풀 수 있다 내가 L 칼로리 이하를 먹어야만한다 그럼 N개의 버거 중 1) 현재 버거를 먹을때 2) 현재 버거를 안먹을때 두개를 비교해주면 된다 이 때 현재 버거를 먹기위해선 칼로리(sum+b[pos])가 L 이하여야 한다! 그럼 그 값들 중 최대값을 찾아보자! 소스코드 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 import java.util.Scanner; public class Solution { public stati..

문제를 읽어보면 그냥 BFS+시뮬레이션으로 풀면 될거같다 심지어 크기도 작다!! 악마->수연 이 순서대로 보내면 수연이가 갈 수 있는곳의 최단거리를 BFS로 구할 수 있다! 큐를 2개만들고 악마큐를 먼저 실행시키고, 수연이큐를 실행시키자 악마가 다음칸으로 갈 수 있는 조건은 .이거나 S이거나이고 수연이가 갈수있는 조건은 .이거나 D이다! 악마가 방문할때마다 *로 바꿔주고 수연이가 방문할때마다 S로 바꿔주면 답이 착하게 나온다!! 소스코드 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 5..

메모리와 시간 때문에 많이 틀린 문제다 풀긴했지만 고칠 부분이 많은 코드같다..! 우선 문제를 보면 결국 딸 이름은 n+m-1의 길이를 가질것이다 그럼 시작점부터 해서 가중치가 제일 작은것만 골라서 끝점까지 가면 된다! 다익스트라! 사용하자 각 자리의 알파벳을 가중치라 생각하고 이름을 찾아가다가 n+m-1 길이의 이름을 찾으면 break를하자! 여기서 break안하면 pq에 너무 많이들어가서 메모리가 터진다 소스코드 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 #include u..

사이클 중 가중치의 합이 가장 작은 사이클의 길이를 출력하는 문제다 N이 크면 다른방법을 쓰겠지만 N이 작아서 그냥 완탐을 돌렸다 모든정점에서 시작해서 해당 정점으로 돌아오는 사이클을 찾고 비교하면 된다 근데 이상하게 가지치기를 하니까 정답이고 안하니까 테케 3개가 틀린다 왜일까..! 가지치기 안해도 다시 시작점으로 돌아올 때 min값을 초기화하면 답이 나올거라고 생각했는데..! 아직 의문이다 ans>sum+cost 이 부분을 빼면 틀린다..! 아시는분..! 소스코드 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 #include using namespace std; #define ll ..

문제가 좀 복잡해 보이는데 잘 읽어보면 dfs를 이용해서 풀 수 있다 먼저 입력으로 들어오는 이름들은 map을 통해 숫자롤 매겨주자 그리고 시너지가 발생하는 조합을 통해 그래프를 만들어준다 그래프를 다 만들었다면 이제 문제는 나와 연결된 정점과 다른색으로 색칠하며 dfs를 돌릴 수 있냐! 이걸로 바뀌게 된다 나와 연결된 정점들에 나와 다른색을 주면서 dfs를 돌아보자 만약 같은색이 있다면 false! 다 돌수 있다면 true 다 하나라도 false가 나오면 No가 답이다 소스코드 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 4..

입력받는 숫자들을 보면 엄청 작다 완탐으로 정말 다 찾아보면 된다 답이 여러개라면 숫자가 많은것 중에 사전순으로 앞에오는 것을 출력해야한다 따라서 각 자리마자 0~x까지 넣어보면서 햄스터 수를 만족하고 현재 답보다 합이 크다면 계속 바꿔주면 된다! 소스코드 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 #include using namespace std; #define ll long long int t,n,x,m; pair arr[11]; int maxcnt; int ans[11]; void solve(int pos,..

BFS를 돌려서 푸는 문제다 성을 넣지말고 반대로 모래를 넣으면 쉽게 풀 수 있다 모래를 기준으로 8방향을 보면서 성이 있다면 1씩 감소시켜준다 만약 성의 견고함이 0이 된다면 모래로 바꾸고 큐에 넣어주면 된다 풀긴 풀었는데 시간이 좀 너무 오래걸렸다.. 왜지..! 소스코드 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 #include using namespace std; #define ll long long int arr[1010][1010]; int dx[8]={-1,-1,-1,0,..

BFS를 이용해서 풀 수 있다 가로->세로 or 세로->가로 이렇게만 이동이 가능하다! 처음에 4방향 그대로 모두 check해줬더니 시간초과가 났다 근데 가로로 온다면 왼쪽에서 오든, 오른쪽에서 오든 똑같다 세로도 마찬가지다! 결국 가로 / 세로 나눠서 2방향으로 보면 시간안에 통과가 가능하다! 그렇게 하기 위해서는 하나는 0 하나는1로 생각하면 된다 4방향을 나누기 2만하면 0,1로 표현가능 하므로 그것만 바꿔주면 된다! 소스코드 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 #..

dp를 통해 색칠해 나갈 수 있다 우선 흰색 검은색 가능한데 동시에 연결된 정점이 (검은색/검은색)은 불가능하다 그럼 이 부분만 잘 처리하면 dfs+dp를 통해 해결할 수 있다! 먼저 나의 색을 저장하고 내가 만약 흰색이라면 내 자식들을 (검은색으로 칠하는 경우 + 흰색으로 칠하는 경우)만큼 가능하고 검은색이라면 (흰색으로 칠하는 경우)만 가능하다 경우의 수 이기 때문에 각 자식들의 수의 곱을 구해가면 된다! long long 조심하자~~ 소스코드 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 #include using namespace std..

방문해야할 곳은 회사 - N개의 고객 - 집 이렇게 12개다 그럼 회사와 집은 고정시켜두고 N개를 next_permutation을 통해 확인하면 된다 10!이기 때문에 시간은 충분하게 나온다! 소스코드 ( Java) 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 import java.util.Scanner; public class Solution { public static int[] order = new int[10]; public static int[][] arr = new int[10][2]..