우리가 흔히아는 스도쿠 문제다 옛날에 처음 풀때는 엄청 어렵게 푼 기억이 있는데 다시푸니까 생각보다 너무 쉽다 그냥 백트래킹으로 숫자 넣어보면서 되는지 안되는지 확인하면 된다 숫자를 넣는 조건은 같은 행,열 그리고 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를 통해 답을 찾아갈 수 있다! 소스코..
문제를 처음 보고 정확하게 어떻게 풀어야 답이 나올지 정리를 못해서 계속 틀렸다 내가 생각한 방법은 무조건 숫자가 들어오면 계속 더해서 보관했다 그렇게하면 합치지 말아야 할 경우에 반례가 생긴다 방법은 작은 숫자부터 그리디하게 보면 해결된다 먼저 내가 받아온 숫자의 합이 n보다 작다면 -1이다 왜냐면 숫자를 계속 나눌수 있어서 1로 나눠서 다 합칠 경우에 어떤수든 성립 가능하다 만약 합이 더 클 때 Bit배열을 만들어서 계속 보관한다 그리고 n의 비트를 0번째부터 보면서 한번 답을 구해보자 만약 Bit[i]가 켜있다면 하나를 빼서 쓰면 된다 여기서 내가 캐치하지 못했던 부분이 있다 아래서부터 보기때문에 이제 더이상 Bit[i]는 필요없다 그래서 Bit[i+1]로 합쳐주면 된다 Bit[i+1] += Bit..