나 요리학원 출신임

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..

bi = (ai*2-1,ai*2)일 때 1~2n 까지 숫자를 두는게 가능한지 보는 문제다 그리디로 내가 앞에서부터 작은수를 채워나가면 된다 이럴때는 upper_bound를 쓰자!! 먼저 set에 1~2n까지 나오지 않은 숫자를 담아준다 그리고 upper_bound를 통해 현재 위치를 만족시켜주는 가장 작은 숫자를 찾자 만약 없다면 -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 #include using namespace std; #define ll long long bool check[222]; int main(){ int t; scanf(" %d",&t); ..

코포할때 풀어서 맞은줄알았는데 56번 테케에서 틀렸다~~! long long 썼어야하는데 안써서 틀렸다~~! 문제를 푸는 방법은 그냥 앞에서부터 쭉 봤다 같은 문자열 더미는 하나라고 생각하면 된다 1~n까지 가는데 드는 총 비용을 먼저 구하자 이 부분에서 long long 나올 수 있다..! 그리고 앞에서부터 보면서 한 더미씩 안갔을 때 총합이 p보다 작은지 확인하자! 소스코드 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 using namespace std; #d..

A,B,C중에 오히려 가장 쉬운 문제가 아니였나 싶다(?) 문제 자체 이해는 어려웠다 S라는 문자열 안에서 등차수열로 이루어진 T라는 문자열을 숨겼다 이 때 문자열 T의 수들 중 최댓값을 찾는 문제다 생각하다보면 문제가 쉬워진다 한번 정리를 해보자 1. 길이가 1일 때 => max(alpha[26]) 중 하나다 2. 길이가 2일 때 => for문을 통해 입력받으면서 보면 된다max(d[26][26]) 3. 길이가 3일 때 => 여기부터 생각해봐야한다 꼭 봐야할까? 길이가 3이상이라면 길이가 2인것들을 무조건 포함해야만 만들 수 있다 따라서 볼 필요가 없다! 2까지만 보면 된다! 그럼 바로 쉬운문제로 변한다! 문제에서 필요로 하는것들만 뽑아내는 능력이 이럴때 쓰이는건가..! 이 문제는 쉬워서 다행히 잘 보..

ABC중에 제일 어려웠던 문제같다.. (0,0) -> (0,x)까지 주어지는 숫자의 길이만큼만 이동해서 가야한다 우선 가장 쉬운경우 1. x길이만큼의 수가 주어지는경우 == 1 2. x보다 큰 수가 주어지는 경우 == 2 (삼각형을 만들면 된다) 3. 위에 둘다 아니라면 그 중에 가장 큰걸로 가보면 된다 만약 나머지 수로 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 #include #include using namespace std; int t; int main..

처음에 문제 이해를 잘못했다 문제는 첫번째칸에 가장 큰 수를 만들라는 문제다 그럼 거리를 보고 만약 다른칸에 수가 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 #include #include #include #include using namespace std; int arr[111]; int ans; int main() { int t; scanf(" %d", &t); while (t--) { memset(arr, 0, sizeof(arr)); int n, m; scanf(" %d %d", &n, &m); ans = 0; for (int i = 0; i

방문해야할 곳은 회사 - 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]..

대회 때 1시간동안 못풀고 끝난 문제다~~! 그리디 처럼 생각했는데 결국 떠오르지가 않는다 그리디와 수학 연습을 해야한다는걸 코포 할 때마다 느끼게된다 먼저 이 문제를 어떻게 접근해야할까 내가 가장 큰 LIS를 찾는다고 생각하면 그건

우리가 흔히아는 스도쿠 문제다 옛날에 처음 풀때는 엄청 어렵게 푼 기억이 있는데 다시푸니까 생각보다 너무 쉽다 그냥 백트래킹으로 숫자 넣어보면서 되는지 안되는지 확인하면 된다 숫자를 넣는 조건은 같은 행,열 그리고 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..

쉬운줄알았는데 좀 고민하게 해준 문제다 먼저 비슷만 문제는 백준의 숨바꼭질 5(https://sejinik.tistory.com/194)다 이 문제는 모든 경우를 DFS로 다 해보면 답이 나오지만 그냥 하면 시간초과 난다 그럼 시간을 줄이기 위해서 어떻게 해야할까? 한번 생각해보자 내가 홀수일때 방문한곳은 다음 홀수에도 방문할 수 있다 반대로 짝수도 마찬가지다 예를들어 123-213-123 이런식으로 2차이나면 원래자리로 다시 돌아올 수 있다 그럼 우리는 방문할 수 있는 숫자 중에서 홀,짝으로 나눠서 방문했는지 체크를 해보면 된다! 내가 만약 다음 방문할 곳에 홀수번만에 갈 때 이전에 홀수번에서 방문했다면 방문하지않는다! 아니라면 방문하면된다!! 그럼 시간안에 dfs를 통해 답을 찾아갈 수 있다! 소스코..