Red Salmon

출처 : https://www.acmicpc.net/problem/1268

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/1268.cpp

이 문제는 풀이를 어떻게 할지 생각을 하였다. 그런데 인풋의 최대가 1000이고 학년은 최대 5이므로 완전 탐색으로 해도 O(5*1000*1000)이니 O(5000000) 이 되므로 충분히 가능하다는 결론을 얻어 완전탐색으로 하였다. 분명 더 효율적인 알고리즘도 존재할것인데, 이 문제는 그렇지 않아도 될거같아서 이렇게 풀었다.

다른 방법으로는 그래프적으로 생각하면 좀 더 편할것 같기도 하다.

나는 먼저 학년별로 A학생과 나머지 학생들의 반을 비교하여 같은 반이면 반을 확인하는 배열을 만들어 계산하도록 하였다. 
역시 이방법도 위험할수있지만, 최대 인풋이 1000이므로 1000x1000을 하여도 충분하였다.

그리고 최대값이 같을경우 가장 작은 번호만 출력하라고 하였으므로 뒤에서부터 검색하여 앞녀석이 나오게 하였다.

역시 그렇게 어렵지 않은 문제였다. 

출처 : https://www.acmicpc.net/problem/2526

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/2526.cpp

이 문제는 과거 풀었지만 재채점으로 오답이 나온 문제다. 그래서 그냥 새로 풀었다. 문제는 어떤 연산을 하였을때 싸이클이 생기는지 물어보는 문제이다. 모든 절차가 간단하고, 어려울게 없다.

그리고 싸이클이 생긴다고하였으니 어떤 수가 중복이 될 가능성은 없다. 중복이 되는 순간이 싸이클이 생기는 순간이다. 그런데 P로 나눈다고 하였고 P는 최대가 97이다. 즉, 값이 98이상은 절대 나오지 않는다. 

그래서 나는 나머지 값을 계속 배열에 담으면서 검사를 하였다. 검사하여 있으면 현재 배열의 총 크기에서 현재 찾은 수의 인덱스를 빼면 싸이클이 되고 없으면 배열에 수를 담는다. 매우 간단한 문제였다.

출처 : https://www.acmicpc.net/problem/2672

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/2672.cpp

음..이문제는 정말 어렵게 풀었다. 사실 풀지 못하였고 다른사람의 코드를 보고 다시작성하였다. 그게 약 9개월 전이고 이번에 복습겸 다시 풀었다.

먼저 문제는 여러 직사각형의 전체 면적을 구하라고 하는데 입력이 소수이다. 배열에 다 때려박고 계산하는식의 계산을 할 수 없다. 이런걸  brute force라고 하는데 이건 알고리즘이 아니다. 

이 문제의 경우 이런식으로 생각하면 이해가 쉽다. 

이런식으로 도형이 나열되어 있다고 생각해보자. 전체 넓이이니 도형들을 세분화시켜서 그 합을 구해도 값은 같을 것이다.

즉 이런식으로 나누게 된다. 

필자는 귀찮아서 선을 전부 그리지 않았다. 더그려야한다. 대략적인 느낌만 알면 된다. 암튼 모든 점에 대하여 선을 나누면 무수히 많은 사각형이 나온다. 이 사각형들 중에 입력으로 들어온 사각형과 비교하여 포함이 된다면 그 값을 계속 더해주면 된다.

이 알고리즘의 경우 O(n^3) 이 되므로  n값이 크다면 역시 올바른 알고리즘이 되지 못한다. 그래서 과거 검색해보니 인덱스트리나 다른 알고리즘을 사용하면 O(lgn) 까지도 줄어든다고 한다. 그런데 너무 복잡하고 어려워서 포기했던 기억이 있다. 

그러나 이 문제를 풀기에는 n^3도 무방하니 이 알고리즘을 사용해도 되겠다. 그리고 범위를 찾는데 다음과 같이

bool chk(double x1, double x2, double y1, double y2, Rect rect)
{
    //return rect.x1x1 && rect.y1y1;
    return rect.x1<=x1 && rect.x2>=x2 && rect.y1<=y1 && rect.y2>=y2;
}
// 두가지 방법이 있다.

위 에 두가지 방법이 있는데 둘중 아무거나 써도 된다. 대부분의 코드를 보니 상단의 방법을 많이쓰고 과거 트리문제를 풀었을때도 저런 비교를 많이 한다. 하단의 방법도 맞으나, 가급적이면 상단의 방법을 쓰면서 이해하는게 응용하기 훨씬 쉬울거 같다.

출처 : https://www.acmicpc.net/problem/1018

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/1018.cpp

이 문제는 어려운 문제는 아니다. 입력 자체도 매우 작다. 그냥 단순 검색이면 끝난다. 내 생각에 이런 문제는 20~30분내에 반드시 풀어야 하는 문제이다. 문제는 올바른 체스판이 되기 위해서 바뀌어야 하는 블럭이 최소가 되는 경우이다.

알고리즘은 다음과 같다.

1. 완벽한 체스판을 만든다. (최상단 맨 왼쪽이 흰색일수도 검은색일수도 있다. 나는 흰색만 생각하여 오답을 맞았다.)

2. 입력받은 체스판의 한점을 기준으로 +8칸씩 하여 완벽한 체스판과 비교를 한다.

3. 완벽한 체스판과 다른점이 있는 최소값을 계속 계산한 후 출력한다.

원래 쉬운문제는 기록하지 않는데 대충 풀다가 놓친부분이 있어서 기록하였다.