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