Red Salmon

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

어딜봐도 저길 봐도 그냥 DP가 아니면 답이 나오지 않을 문제이다.

그리고 숫자 10개를 활용해야한다. 이런문제는 대게 비트연산을 필요로한다.

문제는 0~9까지 모든 수를 활용 하여야 하며 계단식으로 수가 배치되어야 한다. 즉 n번째 수와 n-1 그리고 n+1은 각각 1씩만 차이가 나야한다는 말이다.

이 문제의 접근 방법은 조금 까다롭다. 타인의 힌트를 보지 않았다면 풀지 못했을것 같다. 아직은 공부가 많이 필요하다.

접근방법

1. 먼저 시작값이 0은 아니니 1부터 9까지 돌린다고 가정하고 포문을 돌린다. 

2. 재귀함수를 만드는데 이 함수의 목적은 1부터 n값까지 시작값을 기준으로 길이가 n이될때까지 모든 경우를 만들어보고 이 경우가 조건에 충족을 시키는지 확인하는 용도가 되야 한다.

문제의 접근 방법은 다음과 같다. 여기까지만 이해하면 문제를 풀 수 있다.

코드에서 사용한 부가적인 부분을 설명하자면

int dp[105][10][1 << 10];

이렇게 dp함수를 3차로 만든 이유는 처음 105는 n값이 최대 100이라고 하였기 때문에 누적을 위해서 크게 잡아놨고, 

두번째 10은 각 n번째 수에 대하여 1로시작했을때 2로시작했을때 등등 각 시작값에 대한 경우의 수를 담고 있다.

세번째 표기한 1<<10은 비트연산을 위한 수로써 0~9까지 수들이 전부 사용되고 있는지 체크하기 위함이다.

코드상에서 이문제의 핵심은 12번줄과 13번줄인데, 각각 10미만이면 계속 증가시키고 도달하면 다시 감소시키는 식으로 계속 줄여나가서 경우의수를 만들어준다. 

쉬운듯 어려운문제였다.

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/1004.cpp

문제가 터렛과 비슷한것 같다. 

결국 반지름길이를 이용하고 두점사이의 거리를 이용하여 풀면된다.

두점사이의거리는 피타고라스의 정의로 풀 수 있다.

접근 방법은 다음과 같다.

1. 행성의 중심점과 반지름을 주면 먼저 중심점에서 시작점과 도착점간의 거리를 계산한다.

2. 계산값이 반지름보다 작다면 원에 포함되는 것이다.

3. 각각을 따로 해야한다. 시작점도 넘어서고 도착점도 넘어서면 2개의 행성을 넘어선다는 말이다.

4. 유의할점이 있다면 시작점과 끝점 둘다 한원에 포함될 수도 있으므로 이 부분에 대해 따로 처리를 해줘야한다.

5. 피타고라스정의에서는 루트르 쓰지만 본 문제에서는 루트보다 거리역시 제곱을 해주는것이 정확성을 높이고 실제로 정답을 나오게 한다.

간단한 문제이지만 당황할수도 있는 문제라고 생각하였다.

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

내답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/9813.cpp

하.. 이문제 그냥 간단한 재귀일줄 알았다.. 하지만 매우 손이 많이가는 문제였다. 괜히 정답자가 1명인게 아니었다. 

먼저 나는 정답을 맞지 못했다. 그러나 내 답이 맞다고 생각한다. 정답자 소스에서 반례를 찾았기 때문이다.

먼저 문제설명을 하자면 숫자가 5개 입력이 들어오고 첫번재 수가 -1이면 프로그램이 종료이고 그게 아니라면 계속 입력을 받는다.

수는 1번째부터 4번째까지의 수로 어떻게 계산을 하든 5번째 수를 만들도록 하는것이며 최종적으로 불가능하다면 NO! 를 출력하는 것이다. 

이 문제는 내가 정말 많이 해맸다. 문제 해설이 약간 빈약했던것 같다.

우선 기본적인 접근은 다음과 같다.

1. +, -, *, / 이 네가지 산술기호를 재귀로 전부 할당한다 수는 4개뿐이므로 산술기호는 3개로 한정되어 있다. +++부터 ///까지 모두 대입한다. 

2. 괄호를 칠 수 있다. 하지만 문제에서 하나의 연산자만 가능하다고 하였으니 이중괄호는 없다고 가정하고 시작한다. 괄호는 패턴을 나눠보면 다음과 같다.

//case 1 (a, b), c, d

//case 2 a, (b, c), d

//case 3 a, b, (c, d)

//case 4 (a, b), (c, d)

//case 5 (a, b, c), d

//case 6 a, (b, c, d)

//case 7 a, b, c, d

위와 같이 총 7가지 경우가 나온다.  이 경우에 맞춰 전부 대입해보면 된다. 

하지만 유의할점이 있다.

문제 어디에서도 수가 바뀌지 않아도 된다는 말은 없다. 즉 1번째 수부터 4번째 수까지 위치가 바뀌기도 한다. 

예를들어 a, b, c, d 로는 어떠한 방법으로도 e를 만들 수 없더라도 d a c b 이렇게 순서를 바꾸면 될 수도 있다. 실제로 이런 경우는 존재한다.

그러므로 다시 4가지 수를 모든 경우의 수에 따라 재귀를 돌려줘야한다. 

그리고 두번째 유의할 점

나누기는 언제나 짜증나는 것인데, 만약 예외처리를 하지 않는다면 1/0 이렇게 0으로 나누라는 경우가 발생할것이고 프로그램은 죽게 될 것이다. 그렇기 때문에 반드시 예외 처리를 해야한다.

그리고 3/2 이런수는 당연히 1.5이다. 하지만 int로만 처리하면 이 수는 1이 되고 e가 1이라면 같다고 판단할 수 있다. 그러므로 이 부분도 처리를 따로 해줘야 피해갈 수 있다.

그럼에도 불구하고 나는 오답을 맞았다. 그리고 구글링을 통해 정답자의 소스를 구했는데 특이한 반례를 찾았다.
원문 링크

16 15 17 50 9 다음의 수가 들어오면 나는 ok를 주고 정답자는 no를 준다. 

그런데 이경우 수를 50 17 15 16 9 이렇게 정렬하고 식을 50 / (17-15) -16 이렇게 가공하면 9가 나올 수 있다. 그런데 정답자 소스에는 이 경우 NO를 출력하게 하였다. 아마 이 부분의 차이와 같은 문제로 오답을 맞은 것 같다. 

그런데 신기한건 30 4 2 5 10 이수를 주고 동일한 패턴을 대입하면 정답자소스도 OK를 주게 된다. 뭔가 이건 이상하다.

그래서 나는 내 소스가 맞고 정답테스트케이스 및 정답소스가 틀렸다고 생각했다. 뭐 케이스를 다 열어보고 대조를 해봐야 알겠지만, 확실히 이상한 부분이고 내가 맞다고 생각한다. 

그래서 셀프 정답처리를 하고 넘어가야겠다. 

P.S.

소스를 최대한 간소하게 하려고 함수를 이것저것 써넣으며 반복시켰는데, 그래도 길다...

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/1057.cpp

쉬운문제로 몸풀기용으로 풀었다. 이런건 20분내외로 풀어야 하는 문제이다.

이 문제는 당연히 배열을 만들어서 하나하나 토너먼트 시켜서 계산하라는것이 아니다.
(물론 이 문제는 그래도 답이 나올것 같다.)

단순히 패턴을 좀 보면 된다. 두사람은 만나야하며 반드시 이긴다. 토너먼트는 진행할수록 n이  반씩 줄어든다.

그러므로 둘이 만나려면 한명이 홀수 한명이 짝수여야 하며 토너먼트에서 앞서 있는 사람이 홀수여야 한다.

이 과정에 맞춰 계속 감소시켜주면 결국 만나게 되어 있고 그것을 출력하면 된다. 

뭐 설명도 필요없는 간단한 문제였다.