컴퓨터공부하기

DP

DP를 이용해서 최적값을 찾는다

점수가 40점 미만인 학생의 점수는 40으로 바꿔서 모두 더해주고 평균을 냈다.

규칙이 있다.

i = (i-1) + (i-5) 번째 값을 이용하면 된다.

테스트 케이스마다 계산하는 것이 아닌 미리 한번에 100까지 계산해 놓으면 시간을 조금더 절약할 수 있다.

조건에 맞게 더해주면된다.

생각보다 정답률이 낮은 문제인데 32bit 자료형을 넘어서는 답이 있어서 정답률이 낮은 것 같다.

비교하여 출력하면 된다.

단순하게 비교하는 방법을 이용했다

처음 코드 짯을 땐 시간초과 걸렸다. 시간을 줄이기 위해 노력했다.

kin 변수는 즐거운 날을 기록하는 변수이다

gap 배열은 2차원 배열로 0번째는 즐거운날의 주기를 기록하고 있으며, 1번째는 해당 주기로 몇일까지 왔는지 기록한다.

예시를 보면

1 7 10 13 19 에서

처음 gap[0][0] = 7 - 1 = 6, gap[0][1] = 1 이 되며, 이 의미는 주기가 6인 경우 현재 배열의 인덱스 1이 마지막이라는 의미이다.

다음 값인 10이 주기에 해당하는지 kin[gap[0][1]]번째의 값인 7 + gap[0][0] = kin[2] 인지 확인한다.  13 != kin[2]  이므로 

gap에 다음 주기가 저장 되어있는지 확인한다. 없으면 새로운 주기 등록이 필요하므로 주기를 넣어주고 현재 인덳스를 추가한다.

주기에 의해 중복되는 날이 있을 수 있으므로 29번째 비교 if문에서 주기 확인 후 break를 해주면 안된다.

break를 넣게 되는 경우, 중복 되는 다른 주기가 날짜 갱신을 하지 못해 오답을 낸다( 13개중 11개 맞게 된다)

설명이 부족한 것 같지만... 소스코드를 보면 이해할 수 있을 것입니다.

코드를 조금더 다듬을 수 있을 것 같지만... 그냥 올렸습니다.

해결 원리는

*의 길이가 여러개가 될 수 있으므로 이를 처리하기위해 재귀적으로 코드를 작성했다.

front는 입력 문자열의 앞에서부터 탐색하는 인덱스, end는 입력 문자열의 뒤에서부터 탐색하는 인덱스 이다.

1. end <= front인 경우에는 문자열을 탐색하는 과정에서 틀린 문자열을 발견하지 않고 다 탐색했다는 의미이므로 팰린드롬이 된다. 그러므로 1을 반환한다.

2. front와 end가 '*'이 아닌데 해당 문자가 서로 다른 문자인 경우 팰린드롬이 아니므로 0을 반환한다.

3. front와 end가 '*'이 아니면서 두 문자가 같으면 그다음 인덱스를 탐색하기위해 재귀 호출한다.

4. front와 end가 둘다 '*'인 경우에는

 1) 둘다 없다고 생각하고 재귀 호출

 2) front 나 end 둘중 하나만 없다고 생각하고 재귀 호출

 3) front를 길이 1부터 최대 K까지 해당하는 문자로 보고 재귀호출 ( 길이 K는 end와 end-j가 같지 않을 때 까지 해당한다)

 4) end도 3)과 마찬가지로 생각한다.

5. front가 '*' 일때, end가 '*'일 때에도 4. 와 마찬가지로 반복한다.

나같은 경우는 처음 코드를 작성했을 때, '*'이 여러개 입력으로 주어졌을 때, 제대로 처리가 되지 않았다. 그래서 아래 테스트 입력 예시 마지막 이 Not exist가 나왔었다. 결국 코드를 재귀적으로 바꾸면서 해결했다.

테스트 입력 예제

0번째 출력 n/2번째 출력

1번째 출력 n/2 +1 번째 출력

....