나 요리학원 출신임

문제를 읽으면 그냥 다익스트라처럼 생겼다 그래프를 그리고 내가 최소시간을 들여 원하는 정점으로 가면 된다 근데 조건이 하나 붙는다 100을 초과는 거리를 간다면 그때는 연료를 충전해야 한다 이걸 매번 정점에서 하는줄알고 처음에 틀렸다 ㅎㅎ 결국 내가 갈수있는 거리도 하나의 가져가야할 데이터가 되므로 테이블을 d[정점의 수][갈 수 있는 거리]로 잡아보자 => d[1010][111]; 최대 정점은 1000개고 갈수있는 거리는 한번에 100이다 그리고 다익스트라를 돌리면서 pq에서 내가 남은거리도 들고다니면 된다 만약 남은거리보다 다음정점까지 거리가 같거나 짧으면 그냥 가면된다 하지만 남은거리가 더 짧으면 시간 5를 추가해 충전하고 주행가능거리를 100이라고 생각하자! 그리고 마지막으로 정점 n+1에서 남은..

옛날에 풀어본 문제여서 다시 풀어보려고 했는데 탈탈 털렸다 옛날에는 어떻게 풀었을까? 도움을 받았었나 ㅎㅎ 이 문제는 하이퍼링크는 연결되어있기 때문에 안에서는 비용이 안들고 하이퍼링크를 넘어갈 때는 비용이 든다는걸 그래프로 표현해야한다 어떻게 해야할까..! 그래프를 만들때 (N+M)개의 정점으로 만들어주면 된다! 1~N 까지는 정점이고 (N+1 + M)까지는 바로 하이퍼링크..! 내가 어떤 점 X 가 하이퍼링크 K에 속해있다면 그래프 X에서는 갈 수 있는 하이퍼링크 K에 연결시켜주고 1의 비용이 들고 반대로 하이퍼링크 K 에서는 갈 수 있는 점들 X를 연결하고 하이퍼링크 안에서 이동이므로 비용은 0이 된다! 그래서 그래프를 만들면 X -> K (비용 1) 하이퍼링크 밖에서 이동 (정점 X를 가진 하이퍼링..

오래 고민한 문제다..! 이런거 참 생각을 잘 못하는거같다 어떤 화분을 깨면 화분에 해당하는 숫자가 오른쪽에 임의에 화분에 있다면 그 화분도 깰수있다 계속 연속적으로 이어져간다 자 생각을 해보자..! 맨 처음 화분은 무조건 깨야만한다. 안그러면 아무도 깨주지 않으므로..! 그럼 맨 처음 화분에 포함되는 수를 앞으로 만난다면 그 화분도 무조건 깨져야한다 그럼 입력받으면서 처리할 수 있다..! 화분을 깨지는 수를 계속 저장해가며 하나라도 가지고 있으면 깨버리자! 소스는 참 짧다! 처음에는 set을 썼는데 그럼 시간이 너무 오래 걸린다 배열을 이용하자 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include using namespace std; #define ll long..

참 어려워 보이는 문제다 근데 생각해보면 쉬운 문제다 물론 long long 안써서 처음에 틀렸다 ㅎㅎ 먼저 우리가 알아야할 x들은 소수라는 점을 기억하자 그럼 c1,c3,c5,c6은 소수 2개의 곱이므로 유일한 수 2개가 있을 것이다. 결국 완탐하면 된다! 이 문제에서 x4랑 x8은 의미없다 쓰지 않는다 완전탐색을 할 때 어떤 수 2개를 곱해서 c가 되야하므로 i*ic1>>c2>>c3>>c4>>c5>>c6; vector x1,x2,x3,x4,x5,x6,x7,x8; solve(c1,x1,x2); solve(c3,x6,x7); solve(c5,x2,x3); solve(c6,x6,x5); for(int a=0;a

시간이 충분한 문제다 내가 0일 때 그리고 1일 때 경우를 나눠서 생각하면 된다 먼저 모양의 수는 어떻게 정할까? 유니온 파인드를 이용하면 쉽게 찾을 수 있다 merge할 때마다 해당 부모의 수도 합치면 된다 그렇게 미리 크기를 구해두고 모든 정점에서 만약 해당 정점이 1이면 해당 부모의 크기 0이면 4방향 부모의 합+ 1=>(나를 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 55 56 57 58 59 60 61 62 63 6..

우리가 흔히아는 스도쿠 문제다 옛날에 처음 풀때는 엄청 어렵게 푼 기억이 있는데 다시푸니까 생각보다 너무 쉽다 그냥 백트래킹으로 숫자 넣어보면서 되는지 안되는지 확인하면 된다 숫자를 넣는 조건은 같은 행,열 그리고 3X3 사각형안에 같은 숫자가 없다면 넣어볼 수 있다 그럼 3X3은 어떻게 확인할까? 현재 (x,y)에 있다고하면 우린 (3*(x/3),3*(y/3))을 포함하는 사각형 안에 들어가게 된다 총 /3을 한 9개의 사각형으로 들어가기 때문에 잘 생각해보면 저렇게 나온다 그래서 들어갈 수 있으면 true 아니라면 false로 return 시켜주면 된다! 소스코드 (C++) 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..

DFS+ 그리디를 이용해서 풀 수 있다 우선 지나간 길은 지나갈 수 없으므로 길을 지나갈 때 마다 x로 바꿔주자 그리고 우리가 봐야할 방향은 위부터 봐야 아래 남아있는 정점에 대해 이득이다 따라서 위부터 아래로 시작점에서 dfs를 돌리며 끝까지 가는지 체크를 해보자! 문제의 핵심은 dfs를 조금 변형하는 부분에 있다고 생각한다 내가 만약 x행의 끝부분까지 간다면 true를 리턴해주면 된다! 아니라면 false~~! 결국 도착하는 사람들은 true를 통해 갈 수 있다고 답을 알려준다...! dfs 열공하자 소스코드 (C++) 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 ..

문제를 이해하는데 오래걸렸던 문제다 야구를 하는데 총 N 이닝동안 진행을 하고 나는 선수들이 어떻게 공을 치는지 알고있다 내가 할 일은 순서만 정해주는 것이다! 여기서 조건은 1번타자는 무조건 4번째에 쳐야하고 이닝이 끝났을 때 이전 이닝에 마지막으로 친 타자 다음 타자부터 시작하고 아웃이 3번 된다면 해당 이닝이 끝난다는것! 구현자체는 어렵지 않은데 엄청 헷갈렸다 특히 점수를 매기는 과정에서 나는 배열을 만들어서 구현했는데 이 부분에서 내 앞의 3타자에게 점수를 줄 때는 답이안나왔고 내 뒤에 3타자로부터 점수를 받을 때는 답이 나왔다..! 구현 실수같은데 왜 그런지는 못 찾았다 어쨌든 문제를 풀어본다면! 먼저 순서를 정해야 하므로 next_permutation을 쓴다! 근데 이 때 order[0] = ..

완탐으로 풀 수 있어서 dfs를 이용해 풀었다 팀을 나눈 후 그래프로 표현하고 dfs를 이용해 내가 우리팀에 갈 수 있는지 체크를 하면 된다 여기서 만약 애초에 그래프가 2개 이상의 연결요소로 구성되어있다면 애초에 2개의 팀으로 나눌 수 없어서 -1 을 출력하고 종료하자! 그럼 그래프를 그린 후를 생각해보자 dfs를 이용해서 origin -> next 로 갈 수 있는지 계속 확인해보며 된다 그 후 만약 같은 팀인데 연결 되어있지않다면 false 아니면 true를 리턴해주고 만약 모든 조건을 만족한다면 팀의 합의 최소를 구해보자 소스코드 (C++) 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..

한번 풀어보려고했는데 한시간이나 걸렸따... 문제를 쉽게 해주기 위해 괄호는 하나의 연산자만 포함한다는걸 모르고 풀다가 나중에 보니 답이 다르게나온다~! 그리고 처음에 한자리수만 줘서 더 쉬운것같다 나처럼 복잡하게 푼 사람은 많이 없을듯..! 그럼 문제를 풀어보자! 우선 비트를 이용해서 짝수 인덱스인 숫자만 봐준다 괄호가 짝이 맞아야 하기 때문에 짝수개 있을 때만 넘겨준다! 110101이면 1~2 ,4~6이 괄호다! 괄호를 체크하고 solve 함수로 넘겨준다 그럼 solve는 괄호가 있는곳은 먼저 cal함수로 계산해주고 마지막에 괄호가 없을 때를 계산해 답으로 넘겨준다 cal에서는 순서대로 앞에서 계산하기 때문에 덱으로 그냥 계산했다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ..