Junnnho

문제 : https://www.algospot.com/judge/problem/read/FESTIVAL

문제난이도 : 알고리즘 문제해결전략(하)

이해를 간단히 돕자면

N 일간의 콘서트장 대여비를 미리 알고있는 상황에서 최소 L 개의 팀이 주어졌을때 (팀의 수는 이미정해진팀+@ )

몇일을 대여하는 것이 평균적으로 가장 싼 비용이 되는가 하는 문제이다.

* 단, 연속해서 대여해야 한다.

문제를 접근해보자면

눈에 띄는 것이 연속해서 대여한다는 점이였다.

결국 구간합에대한 구간크기의 길이로 나눈 값이 제일 작은 비용을 찾으면된다.

N의 범위는 1-1000이고 시간제한은 2초, 테스트케이스는 최대 100개

그냥 무난하게 2중포문으로 반복문만 돌려도 100N^2 이여서 무난히 시간을 통과할 것 같았다.

나는 간단히

1 2 3 1 2 3 이라는 대여값을 받으면

1 3 6 7 9 12 이렇게 값을 연속으로 더해놓고,

L의 최소값부터 L 이 N 이 될때까지 반복문을 통해서 구현하였다.

https://www.acmicpc.net/problem/4673

문제 해결에 필요한 알고리즘 : 소수(?)

특정 자연수에 대해서 생성자(자신을 만들어낼 수 있는 수) 가 없는 수를 셀프넘버 라고 한다는데

문제 힌트는 분명 소수 라고 되어있긴한데 소수로 어떻게 문제를 해결하는 것인지는 잘 모르겠고

그냥 각 수 마다 셀프넘버를 찾는 방식으로 문제를 해결하였다.

10000까지의 셀프넘버를 찾으면 되니

10000까지 전부 셀프넘버가 아닌 것으로 초기화하고

각 숫자마다 셀프넘버인지 확인 후, 반복문을 통하여 답을 출력하였다.

LCS(longest common sequence) - 공통되는 최장 부분수열

string f = ACAYKP

string s = CACANK

이렇게 두 문자열이 있다면 공통되는 최대 길이의 부분수열은 A C A K -> 4 가 된다.

LCS 는 DP 를 통해서 구현되며

LCS4 번 문제같은 조건이 주어진 숫자의 경우 lis 알고리즘으로 해결한다.

(나중에 공부하고 포스팅해야지)

기본적으로 두 문자열에 대한 dp[][] 를 선언으로 시작한다.

한 문자열에 대해서 다른 문자열의 각 문자를 전부 비교한다.

f[i] == s[k] 이면 dp[i][k] = dp[i-1][k-1]+1;

f[i] != s[k] 이면 dp[i][k] = max(dp[i-1][k], dp[i][k-1]);

************************************************************************

부분수열이 아닌 문자열을 찾는 것이라면

f[i] == s[k] 이면 dp[i][k] = dp[i-1][k-1]+1;

위 점화식을 이용하여 공통된 문자열의 최대 길이를 찾을 수 있다.

ex)

ACACK

CACIP

--> CAC : 3

************************************************************************

2번 문제는 살짝 수학문제 푸는 느낌

* 공의 지름보다 작은 장애물을 넘을 때 계산과정 *

지름보다 같거나 큰 장애물을 넘을 때는 그냥 반지름에 대한 90도의 호 길이만 구할 줄 알면 되는데

중요한 것은 지름보다 작은 장애물을 넘을 때는 호의 이동 길이가 달라진 다는 것이다.

* 종이에다가 지름보다 작은 장애물, 공을 그려놓고

  어떻게 움직이는 지 확인해보자.

  원의 방정식 (x-a)^2 + (y-b)^2 = r^2 을 안다면

  쉽게 해결할 수 있는 문제!