브루트포스2 BOJ 1034 - 램프 https://www.acmicpc.net/problem/10341차 시도처음 그리디를 이용하여 0의 개수가 가장 많은 열을 스위치 작동시키는 방법을 구상했다.O(N*M)이 걸렸지만 스위치 작동 후의 0을 구하는 과정과 켜진 행을 찾는 구간 때문에 시간 초과가 발생했다.더 빠른 방법을 구상해보기로 했다.2차 시도우선 규칙이 보였다.한 행에서 0의 개수가 k보다 크면, 해당 행은 완전히 켜질 수 없다.한 행의 0의 개수와 k의 홀짝이 다르면, 해당 행은 완전히 켜질 수 없다.2번의 경우, 밑에 예시로 보자3 30101011014일 경우, 2번째 열을 홀수번 킬 때 2,3번 행이 완전히 켜지게 된다.그러나 k가 짝수이기 때문에 2,3번 행은 처음과 같은 상태가 된다.3 30101011013반면, k가 홀수가.. 2024. 10. 28. [랜덤] BOJ 1091 - 카드 섞기 https://www.acmicpc.net/problem/1091 아이디어: 10분코딩: 15분 접근법카드를 석는 방법대로 카드의 위치를 옮기는 것이 핵심인 문제이다.이는 직접 과정을 하나하나 하다보면 점화식을 구할 수 있다. 먼저 현재 카드를 before={0, 1, 2, 0, 1, 2}이고, 섞는 순서를 S={1 4 0 3 2 5}라고 가정해보자. 그리고 섞은 후의 배열을 after[]라고 하자. S를 0번부터 ~5번까지 돌면서 각 상황을 보자. before의 S[0]번째 카드는 after의 0번으로 이동해야한다.이를 식으로 표현하면 after[0] = before[S[0]] before의 S[1]번째 카드는 after의 1번으로 이동해야한다.이를 식으로 표현하면 after[1] = before[S.. 2024. 10. 25. 이전 1 다음