SLENDER ANKLES's 개발블로그

쫌 고민을 많이 했다. 

우선 문제를 간단히 정리하자면

1<= x <= 999999 의 숫자가 입력되면

이 수에 포함되어 있는 숫자들을 이용하여 만든 수들 중에 입력된 수보다 큰 최소수를 구하는 문제이다.

다소 문제 설명이 어렵지만,

156을 보자면 156이 포함되어 있는, 156의 자리수로 만들 수 있는 숫자는

156, 165, 516, 561, 615, 651 등등이 있다. 

이 중 입력된 156보다 큰 최소 수는 165이다.

문제 풀이)

처음에는 어떻게 풀어야 되나 굉장히 고민을 많이 했다. 156의 자리수를 가지고 만들 수 있는 수들을 다 구한다음에 정렬하고, 

입력받은 수 보다 큰 숫자를 출력해야 되나? 가 첫 번째 떠오른 방법이었다. 일단 1~999999이기 때문에 숫자를 만드는 방법에 대해서 어려운 점이 있었다.

한번 더 생각해보니까 

1~999999까지 for문을 돌리면서 조건을 만족시키는 숫자를 캐치해내면 되겠다고 생각했다. 

예를 들어 156이 입력되면

1) 156~999999까지 반복문을 수행한다.

2) 각 숫자들마다 자리 수에 있는 숫자들을 판별하여 1,5,6에 부합한지를 체크한다.

3) 만약 조건에 부합하면 바로 출력하고 프로그램을 끝낸다.

4) 조건에 부합하지 않으면 0을 출력한다.

문제정리)

- 시작은 계단으로 치지 않는다.

- 한계단 또는 두계단 씩 오를 수 있다.

- 연속되게 세개의 계단을 밟을 수 없다.

- 계단을 밟을때마다 점수가 오른다.

- 마지막 계단은 반드시 밟아야한다.

- 얻을 수 있는 점수의 최대값을 구하라.

문제풀이)

dp[계단의번호][1] => 지금 계단을 바로 전 계단에서 한 칸 오르는 경우의 최대 값

dp[계단의번호][2] => 지금 계단을 바로 전전 계단에서 두 칸 오르는 경우의 최대 값

초기 계단의 번호 0 과 1은 값을 지정해 준다.

dp[1][1] = arr[1]; dp[1][2] = 0;

dp[2][2] = arr[1] + arr[2]; dp[1][2] = arr[2];

3번 계단부터는 점화식을 통해 dp를 수행한다.

dp[i][1] => 지금 계단을 한 칸으로 오른 경우

dp[i][1] = dp[i-1][2] + arr[i];    => 전 칸까지 2칸으로 오른 경우의 최대 값에 지금 계단의 값을 더함

dp[i][2] => 지금 계단을 두 칸으로 오른 경우

dp[i][2] = max(dp[i-2][1], dp[i-2][2]) + arr[i] => 두 칸 전까지 오른 경우의 최대 값에 지금 계단의 값을 더함

재귀 함수를 사용해서 

2진 검색을 수행했다.

문제 요약)

1. 동점자수를 고려해서 정렬하라.

2. 원래 입력 했던 순서대로 등수를 출력하라.

문제 풀이)

구조체를 활용해서 풀었다.

구조체에는 원래인덱스, 점수순위인덱스, 점수 정보를 담았다.

(1) 점수를 입력받으면서 원래인덱스를 저장했다.

(2) 점수 별로 정렬했다.

(3) 여기에 점수순위인덱스를 갱신했다.

(4) 원래인덱스 별로 정렬했다.

(5) 출력

소수 결정 알고리즘을 사용 할 줄 알아야 하는 것도 핵심인 거 같다. 

그 이외에는 몇 가지 예외를 처리하는 식으로 문제를 풀었다. 좋은 방법으로 푼 것은 아닌 것 같아 조금 더 연구를 해봐야 할 것 같다. 

하지만, 더블릿에서 실행 속도 3등을 했다.!!!

설명하기 전에 소수 판별 알고리즘에 대해서 간단히 다시 정리하겠다. 

문제정리)

자연수 n(2이상 1 000 000 000이하)의 자연수가 주어지면

그 것을 소인수 분해하는 것이다.

풀이)

1부터 10000정도까지 소수들의 데이터를 배열에 저장 해 놨다. 굳이 말하자면 소수들에 대한 데이터베이스를 구축해놓고,

열람하며 활용하겠다는 방식이었다. 낭비라는 생각도 들었지만 결과론적으로 이 방법이 꽤 빠르다는 것을 알았다.

그다음부터는

수학공식에 있던 방법을 고대로 가지고 와서 코드로 옮기는 방식을 사용했다. 

매번 지금 계산 되고 있는 것이 소수 인지 판별한다. 소수이면 중단하고 소수가 아니면 소수리스트의 값으로 나누어준다.

이 과정을 반복하게 된다.

위와 같은 식을 인수분해 한다.

입력

예시를 참고하시오

(x-p)(x-q)일때 p <= q이어야 한다.

풀이정리)

(x-p)(x-q)를 펴보았다. x2 -(p+q)x + pq로 펴진다.

p+q == a && pq == b

를 만족하는 p, q를 2중반복문을 사용하여 답을 도출하면 끝

쉬운 문제였다. 피타고라스 정리는 이렇게 풀리지 않는 것이 안타깝다.

c라는 정수가 주어졌을 때 

a제곱 * b제곱 = c제곱

인 a, b를 찾는 문제였다. 

c제곱 - a제곱 = b제곱 이라는 것을 이용하여

a, b for문을 두 개 이용하는 것이 아니라 a에 대한 for문 한 개만 이용하여 푸는 방법인데

c제곱 - a제곱의 sqrt(루트)가 자연수이면 그 것은 성립된다는 것으로 생각하면 된다. 

문제는 소수점에 대한 double형인지 소수점 없이 나누어 떨어지는지에 대해서 알 필요가 있다고 생각했다. 

소수판별은 c제곱 - a제곱인 b제곱인 b를

다시 a제곱 * b제곱 == c제곱 인지 검사해줬다.

이렇게 되면 b가 소수점이 나오게 되면 다른 값이 나올 테니까...

테스트케이스 7개까지 통과 했다. 

이 테스트케이스에서 막혔다 ㅡㅡ ㅜ

118276

다시 풀어 봐야 겠다.

--------------------------------

풀렸다

실수를 했다. a에 대한 for문을 돌리면서 습관적으로 int형으로 선언한 뒤에 돌렸다.

생각해보니까 long long으로 선언해서 돌려야 한다. 

for(long long a = 1; a < c; a++)

이런식으로 돌려되는 것을 long long이 아닌 int로 선언해서 된 오류였다.

이 문제를 푸는 데 정말 많은 시간이 걸렸던 거 같다. 

우선 문제에 대해서 간략이 정리하자면, 

'(' 또는 ')', '[', ']'로 구성된 문자열들이 입력으로 주어진다. 

() => 2점 , 

[] => 3점, 

(X) => X*2점, 

[X] => X*3점, 

XY => X + Y의 규칙을 가진다. 

이 점수를 계산하라는 문제였다. 

문제의 핵심은 괄호들을 stack에 쌓이면서 중간중간의 연산된 값 역시 같이 스택에 쌓는 것이다. 

또 문제에서 잘못된 입력에는 0을 뱉으라고 했으므로 이에 대한 조건이 필요하다. 

예외) 

(1) 모든 입력에 대한 연산이 끝났는데도 stack에 괄호가 남아있을 때

(2) 연산도중 stack에서 짝이 안 맞는 괄호가 나왔을 때 

(3) 연산도중 stack이 비어 버릴 때

이렇게 3가지 정도의 예외를 하드코딩으로 박아줬더니 답이 나왔다. 

STACK을 사용해야겠다는 직감을 가져야 하는 문제이다. 

약간의 생각이 필요한 듯 싶다. 그래서 정답률이 20% 대 인거 같다.

나는 이 문제에 대해서 실마리를 듣고 나서 풀었다. 

다시 풀었더니 그래도 잘 안 풀렸다. 이런 문제는 몇 번 더 풀어봐야 할 꺼 같다. 

문제의 조건에 맞추어 입력값들이 최대 50000개정도는 들어 온다고 하였으므로 다음과 같은 변수자료들을 선언했다.

STACK과 result[500005]

송신탑을 입력 받으면서 몇 가지 조건문을 통과해야 한다. 

1) 만약 스택이 비어있다면 result[현재인덱스] = 0 으로 저장되며

지금 있는 값은 stack에 저장한다.

2) 만약 stack의 top이 현재입력값보다 크면 stack의 top의 인덱스가 result에 저장된다.

3) 만약 stack의 top이 현재입력값보다 작으면 stack의 top은 pop된다. 

이와 같은 프로세스를 거쳐주게 되면 답을 구할 수 있다.