SLENDER ANKLES's 개발블로그

문제를 제대로 읽고 답하면 어렵지 않게 풀 수 있는 문제였다. 

책의 ISBN은 10자리수로 구성되는데 

1~9번째 자리까지는 0~9의 수들로 이루어져있고

10번째 자리는 0~10(10은 X로 표현됨)으로 이루어져 있다. 

입력 받은 수에 ?가 끼어있는데 이 물음표를 구하는 문제였다. 

우선 캐릭터 배열보다는 INT형이 관리하기 쉬웠으므로 INT형으로 바꿔주어 입력 받고, 

물음표는 -1로 배열에 저장하였다. 

규칙에 맞게 각 자리수를 더해서 SUM을 만들고, 

물음표가 들어온 자리의 인덱스를 저장해두었다가

순회하며

SUM + (물음표자리수에 해당 하는 숫자 * 맞출숫자)   를 11로 나누어서 0이 되는 값을 찾았다. 

코딩 해줘야 할 것이 많지만 , 그리 어려운 문제는 아니었다. 

다만 구현하는데 시간이 좀 걸렸다. 이런 문제는 시간 싸움인 것 같다. 

문제에 대해서 간략히 정리하자면

19 * 19 배열을 오목판으로 생각하고 흰돌, 검은돌이 배열 위에 그려지게 되는데

지금 상황에서 흰돌이 이긴 것인지, 검은 돌이 이긴 것인지 판별한다. 알 수 없으면 0을 출력한다.

오목은 반드시 돌 5개가 나란히 놓여야지 이기는 것, 6개가 놓이면 이기는 것이 아니다. 

만약 돌 5개가 놓인 지점의 가장 끝 부분(좌우 라면 가장 좌, 상하라면 가장 상)의 좌표도 출력하라.

문제에 나온 조건 대로 코딩해줬다. 

코드는 100줄을 넘어가게 되었지만 나름대로 줄인다고 줄여봤는데 문제의 조건을 표현하는데만해도 꽤 많은 코드가 

필요하므로 당연한 것 같다. 

문제를 푸는데는 약 1시간 넘게 걸린 것 같다. 

중요한 조건이라고 생각되는 것은 오목에서 이기기 위해서는 반드시 돌 5개가 연결되어야만 한다는 것이다.

그래서 반드시 5개만 연결된 것만 답이라고 생각하고 구현했다. 5개 이상은 아니다!

처음부터 끝까지 접근방법은 

어느 한 돌을 만나면 

돌을 색깔을 인자로 가지는 재귀 호출을 하는 것이었다. 

방향은 

1) 좌우, 2) 상하, 3) 좌상우하 , 4)좌하우상

이렇게 크게 4가지의 단위로 검색을 하면 된다. 

그래서 맞으면 값을 도출하고, 재귀호출시에 가장 최소 좌표를 찾아놓으므로 맞춰서 같이 출력해주면 답이 나왔다.

하지만 더블릿에서 다른 사람의 맞춘 소스를 보고 느낀 것은 내 코드에 쓸데없는 조건들이 좀 많이 들어간 거 같다. ㅜㅜ 

담백한 코드를 짜고 싶었는데,,

소수관련 문제였다. 

4보다 큰 수는 반드시 소수 2개의 합으로 표현된다는 것이 골드바하의 추측이라고 한다. 

이러한 수는 

n = a + b 로 표현가능한데, 여러개의 답이 나올 수 있으므로 b - a가 최대인 것을 찾으라는 것이다.

수행시간이 깡패적으로 많이 나온 방법을 택했는데, 그래도 모두 테스트케이스 당 1초안에 문제를 풀어내었다.

소수에 대한 데이터베이스를 만들어서 답을 만드는 방법이었다.

1) 1~n까지, 소수를 만들어 줬따.

2) 답은 b - a가 최대인 값이라고 했으므로

a는 소수모임의 처음부터 for문을 돌고, 

b는 소수모임의 끝에서부터 for문을 돌았다. 

답이 나오면 바로 종료하게끔 해주기 위한 것이었다. 

이 문제를 통해서 소수를 만드는 방법에 대해서 좀 더 정확하게 구현하고 알게 된 것 같다.

DP를 통해서 답을 도출해야되는 문제였는데, 

나는 생각해내지 못 해서 안타깝다. 같은 스터디를 하는 사람 코드와 설명을 듣고 풀게 되었다. 

문제정리)

다음의 두 조건을 만족시키게 색종이를 쌓아야 한다. 

1) 새로 올려 놓는 색종이는 맨 위의 색종이보다 크지 않아야한다. 맨 위의 색종이 밖으로 나가서는 안 된다. 

2) 새로 올려 놓는 색종이와 맨 위의 색종이의 변들은 서로 평행해야 한다. (색종이를 90도로 회전은 가능하다)

문제풀이)

입력으로 주어지는 색종이들의 개수의 제한은 100개이다. 

모든 경우의 수를 완전탐색으로 할려고 했는데 좋은 방법은 아닌거 같다고 생각했다. 

우선 몇 가지 이슈에 대해서 정리해보자면, 

구조체를 정렬해야 한다. 

근데 문제에서 가로(x), 세로(y)의 입력이 주어지는데 

색종이는 90도로 회전 가능하다고 했으므로 x와 y가 바뀔 수 있고, 그 순서가 큰 의미가 없다고 판단 할 수 있겠다.

그래서 입력의 가로 세로 중 큰 값을 x에, 작은 값을 y에 넣어주었다. 

또는 그 반대로 해도 상관 없다.  

그리고 다음과 같은 방법으로 구조체를 정렬해주는 팁이 있는데, 진선이를 통해서 알게 됐다.

위 방법은 구조체를 작은 수를 앞쪽(오름차순으로 정렬을 하고자 할 때 사용한다)

이 방법은 <algorithm>헤더의 sort를 충분히 이용 할 수 있어서 좋은 것 같다. 

이렇게 준비가 다 끝나면 

첫번째 색종이 이후에 두번째 색종이부터 순회하면서 

매번 자신 색종이 전까지를 체크하면서 

앞의 색종이보다 자신이 크면 색종이 쌓는 개수를 1개씩 증가시켜주어 결과값에 저장시켜주는 

메모리에 저장하는 일종의 dp방법을 사용하여 답을 구해주면 된다. 

그 동안 난해했던 이러한 류의 코딩하는 방법을 조금은 터득한 것 같아 정리해둘려고 한다. 

1) 항상 몇 가지 나열된 원소(숫자)를 중복을 허락하지 않고 모든 경우의 수를 구해야 할 때, 

=> n!

2) 몇 가지 나열된 원소(숫자)로 만들 수 있는 모든 경우의 수 구하기

=> n * n * n * n * ......

위와 같은 수행과정이 필요할 때 재귀적으로 코딩하는 것이 만만치 않았다. 

단지 for문을 돌면서 수행 할 수도 있다.(완전 탐색의 원소의 개수를 완벽히 알 수 있을 때 말이다.)

하지만 그렇지 않을 때에는 난 감했던 적이 많았는데 다음과 같이 코딩해주면 된다. 

이 것은 지속적으로 반복기억해주어야 겠다.

3) m가지의 수들로 n자리 수를 중복을 허락하여 만드는 경우

m * m * m( ... n번)