TOPCIT 알고리즘 시험 후기

음..

문제의 내용을 적어도 될거라 믿고 적을게요.

1번 문제는 양과 염소가 있는데 먹이가 같다.

먹이를 먹는양은 염소 1마리당 A그램 양 1마리당 B그램 먹고,

둘이 합쳐서 N마리이고 전날 M그램을 먹었다.

입력값이 A B N M으로 주어지고,

염소의 마리수를 구하는 거다.

시간복잡도는 O(N)으로 풀이했다.

2번 문제는 1~100점으로 점수가 돼있고, A B명이 있을 때

A B 각 data들을 곱해서 최대가 나오는 수를 구해라.

즉 A[1]~A[i] * B[1]~B[j]를 하나씩 하나씩 곱하는건데, 하나씩 곱해서 더한값이 가장 큰 수를 구하는거다

1 3 5

5 3 1이면

5 * 5 + 3 * 3 + 1 * 1 이 최댓값이다.

풀이는 정렬해서 풀면 시간초과가 난다.

그래서 1~100이 들어가는 정렬을 만들고 나올때마다 ++해주고, 차례대로 곱해준다.

의사코드로 적어보면

while(d[a]==0) a++

result+=A[a]*B[a];

A[a]--,B[a]--

뭐 이런식으로 구현하면 O(N)이다.

3번문제는 풀었는지 못 풀었는지 기억이 안난다.

근데 문제와 풀이 방식은 기억이 나서 적어본다.

사람들이 줄을 서 있다.

1번째 줄에는 k명

n번째 줄에는 k+n-1만큼 있다.

i번째 사람이 j줄에 있을때 몇 번째만에 k를 구하냐와 k를 못 구하면 -1을 출력한다.

내가 푼 공식은

mink와 maxk를 구하는 거였다.

mink를 구하는 방법은 k가 마지막에 있다고 가정하고, n-1을 i에 빼주고 i를 j로 나누면 mink가 나온다.(근데 이거는 문제가 있는거 같음)

maxk를 구하는 방법은 mink를 하는것처럼 하는데, i번째가 j줄의 시작이라고 가정하고 한다.

반복문을 돌면서 mink와 maxk가 같아지면 답을 출력하는 아이디어다.

4,5,6,7번 문제는 아이디어가 있는데

회식하고 다음날이라 못풀었다. ㅠ 나중에 문제가 뜨면 풀어야지