공부방

로봇이 이동하는 모든 경로를 다 돌아보면서 그 경로가 단순한 경로일때만 그 경로가 나올 확률을 계산해서 더해주면된다. 로봇이 이동하는 경로의 수는 $$4^N (N=14일때 약 2.6억)$$ 이라서 시간초과가 날 것 같지만, 방금 왔던 방향과 반대방향으로 가게되면 바로 단순경로가 아닌셈이 되므로, 사실상 $$3^N (N=14일때 약 5백만)$$ 개의 경로에 대해서만 확률을 계산하면 된다. #include using namespace std; int N, east, west, south, north; double possibility[4]; int dx[4]={0, 1, 0, -1}; int dy[4]={-1, 0, 1, 0}; bool movingArea[29][29]; double pos; //move=..

특성값 두 개를 골라서 0에 가장 가깝게 만들어야 한다. 주어지는 특성값 배열이 정렬되어 있다. 이런 상태라면 배열에서 최솟값과 최댓값을 정답의 후보가 될 수 있다. 예를 들어 [-99, -2, -1, 4, 98] 에서 배열 내의 최솟값 -99과 최댓값 98의 합은 정답의 후보라고 생각할 수 있다. 예시에서는 우연히 정답이지만 정답이라고 확신할 수는 없다. 하지만, 여기서 배열이 정렬되어 있다는 특성을 이용하면 문제 해결의 실마리가 보인다. -99와 98의 합은 -1이다. 이 결과에서 두 개의 용액 중 하나는 반드시 -99를 고른다고 가정했을 때, 특성값의 합의 최대값은 -1이라는 것을 알 수 있다. 반대로 두개의 용액 중 하나는 반드시 +98을 고른다고 가정했을 때, 특성값의 합의 최솟값은 -1이라는 ..

어떤 행이 반드시 켜져야한다고 생각하자. 그렇다면 그 행을 키는 방법은 단 한가지 밖에 존재하지 않는다고 생각할 수 있다. 만일 불이 꺼져있다면 스위치를 누르면 되고, 불이 켜져있다면 스위치를 건드리지 않으면 된다. (하나의 스위치를 두번 누르는 것은 결국 스위치를 조작하지 않은 것과 같다는 것을 생각하자) 모든 행을 돌아보면서 돌아보는 행이 모두 켜져있다고 가정을 하게 되면 모든 열에 대해 스위치를 누르는 방법이 결정된다. 그걸 이용하면 브루트포스 방식을 이용하여 문제를 풀수있다. #include #include using namespace std; int change[51]; int numbers[52][52]; int N, M, K, ans; int main(){ ios_base::sync_with..