Red Salmon

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

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

컨디션 난조로 적당히 할만한 문제를 잡았다. 이 문제의 경우 정보 올림피아드 출제 문제이다. 

나는 2가지 풀이법이 떠올랐다. 분명 더 훌륭한 알고리즘도 존재할거라고 생각한다.

우선 첫번째 알고리즘은 1000x1000배열을 생성한 후에 입력받은 값만큼 상자를 만들고, 왼쪽 맨아래를 0,0이라고 할때 x값을 증가시키면서 1을 발견하면 다시 위로 올가다가 끝이면 다시 오른쪽으로 가는 식으로 하여 1을 계속 채워나갈생각이었다. 최대 높 이에 도달하면 그 아래로 내려갈수가 없으니 끝까지가고 다시 맨뒤 막대부터 시작하려고 했다. 이렇게하면 정렬을 할 필요가 없는 장점이 있었다. 

암튼 이런 풀이를 하게 되면 문제에서 표기된 검은 라인이 생성될텐데, 이제 다시 검색을 시작하여 1과 1사이에 있는 모든 것들을 체크해주면서 카운팅을 해주면 정답이 나오겠구나~ 생각했다. 하지만 L과H가 10000이라면? 이건 풀수가 없게 된다. 왜냐면 배열값을 넘어버리기 때문이다.

그래서 두번째 방법을 생각했다.

결국 사각형의 넓이합이 아닌가? 선이 꺽이는 순간 2개의 x값의 차를 통해 밑변을 구하고 윗변 길이를 곱하여 sum을 계속 더해나가는 식으로 계산했다. 이게 훨씬 간단하고, 더 큰 크기에서도 잘 작동할것 같았다.

넓이의 최대값은 (1000x1000)이니까 백만이 최대가 되어 int로도 충분히 표현이 가능했다.

하지만 한번에 정답을 맞지는 않았는데, 놓치고 있는 부분이 있었다.

만약, 높이가 같다면?? 즉 나는 초기 풀이에 반드시 높이가 달라진다고 생각하였다. 하지만 혼자 테스트케이스를 만들어 테스트해보니 값이 맞지 않았다.

예)

5

1 11

2 11

3 11

4 11

5 11

이때 55가 나와야한다.

항상 소스를 간략화하고 줄이려다보니 나온 실수였다. 다음부턴 이런 실수를 하지 않도록 주의해야겠다.

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

해답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/1874.cpp

예전부터 풀어야지 하며 안풀었던 문제를 드디어 풀었다. 엄청 간단할줄 알았는데 생각외로 해맸다. 졸려서 그런거 같다.

이 문제는 이름만 봐도 스택을 써야할듯한 문제이다. 내용도 스택을 쓰세요~~ 라고 말하는것 같다. 하지만 경험상 스택문제의 경우 거의 대다수는 스택이 필요없고 배열로만 할 수 있으며, 훨씬 속도면에서 빠르다. 구현도 훨씬 쉽다. 그러나 큐나 리스트같은경우는 배열로는 답이 나오지 않는 경우가 대다수이다.

이 문제에 먼저 기억해야할 점은 불가능한경우 NO를 출력하라고 한 점이다. 불가능할 경우가 있다는 말이니 예외처리를 해줘야한다. 나는 역시 이부분을 놓쳤다가 나중에서야 다시봤다. 하지만 이번엔 빨리 캐치해냈다.

풀이를 살펴보면 다음과 같다.

1. 입력을 받아 스택의 최상단 값과 비교를 한다.

2. 입력값이 최상단 값보다 크다면 현재 사용된 가장 큰 수부터 입력값까지 스택에 새로이 쌓는다.

3. 그 후에 최상단 값과 입력값을 비교한다.

4. 일치하면 최상단 스택을 지워버리고, 일치하지 않는다면 불가능한 경우다.

여기서 설명을 덧붙이자면 스택에는 현재 숫자의 입력에 따라 순차적으로 쌓여있다. 그런데 입력값이 스택의 최상단 값과 일치하지 않는다는 말은 스택의 순서를 무시한 경우이거나, 이미 사용된 수이거나, 전혀 관련없는 수일가능성이 높다. 그렇기 때문에 불가능한 경우가 된다. 이해가 되지 않는다면 역시 손으로 써보면서 증명해보는게 최고다. 그리 어렵지 않은 문제였다.

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

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

이 문제는 굉장히 쉽다. 그러나 나의 고질적인 문제인 대충읽기로 인해 굉장히 해맸다. 그래서 기록해야겠다고 생각했다.

 먼저 문제는 입력의 쌍이 들어오고, 여기서 덩치순위를 정하는 것이다. 나는 문제를 대충읽고, 정렬이 답이라 생각했다.

stable_sort를 통해 정렬을 시키고 바로 다음 인덱스와 크기를 비교하여 다르면 rank를 갱신하고 둘중 하나만 같으면 rank를 그대로 가는 방식으로 값을 매겼다. 물론 pos라는 값을 카운팅해주며 rank가 변할때 앞에 몇사람이 있었는지 체크하였다. 

그런데..오답을 맞았다. 직감적으로 이건 또 내가 문제를 잘못읽었겠구나 생각하며 천천히 정독하였다.  역시나..

문제에서 등급을 매기는 방법은 

 만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다.

이라고 한다. 즉 정렬도 필요없고 입력받은 사람들의 데이터들을 쭉 찾으면서 자기보다 큰사람이 몇사람이나 있는지를 체크하는 것이었다. 매우 간단했다....

이런문제에 40분가량을 소요한것이 매우 우둔하며 후회스럽다. 과거 이런 습관으로 인해 큰시험에서떨어졌으면서 바뀌지 않는걸 보니 이 문제를 자각하지 못하고 있는것 같다. 쉽더라도 집중해야 한다는걸 기억하기 위해 풀이를 적었다.

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

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

이 문제는 가볍게 보면 정수 a, b, c 3개를 입력 받는다. 그리고 pow(a, b)%c를 하면 끝이다. 하지만 이렇게 쉬운문제는 풀지도 않는다. 이 문제의 요건을 보면 a, b, c전부 INT_MAX의 인풋을 받는다.

즉 최악의 경우 pow(INT_MAX, INT_MAX)의 경우가 발생한다. 당연히 이런 문제는 머리를 쓰라는 것이다.

전에 공부하면서 math.h에 담겨있는 pow함수는 단순 반복문으로 만든 함수가 아니라는걸 알았다.(확연한 속도차이)

그래서 과연 stl의 pow는 어떻게 구현이 되있나 생각해봤다. 맞는지 아닌지는 모르겠으나 내가 생각한 방법도 상당한 속도를 가진다. 

예제를 살펴보면 10 11 12 가 인풋으로 들어오고 이는 pow(10, 11)%12이다.

그런데 10^2는 100이고 100^2 는 10000인데 이는 10^4이다. 그리고 10000에 다시 제곱을 하면 결국 10^8이 된다. 

이렇게 3번만에 10^8까지 구하였다. 10씩 8번 곱하는 경우보다 훨씬 계산이 줄었다.

그리고 현재 2의 제곱씩 경우의 수를 늘려가고 있기 2^3인 8을 현재 b에서 뺀다.

남은 3은 다시 위과정을 반복한다. 

이렇게하면 매우 적은 연산으로 값을 추출할수있다.

그리고 이문제에서 주목해야할 점은 long long이어도 20억이상의 수를 곱하다보면 값이 넘어서버릴가능성이 있다. 

여기서 (a+b) mod c = (a mod c + b mod c) mod c 식을 응용하여 계속 값을 줄여준다.

그러면 답이 나온다. 이 설명이 이해가 되지 않는다면 인풋을 2 6 100 이런식으로 해서 계산해보면 이해가 될것이다.