[강원대학교] 교내 프로그래밍 대회 본선 후기

구름에서 5문제 2시간이었습니다.

한 문제를 제외하고는 골드 수준으로 풀만했습니다.

 

1번은 큐랑 우선순위 큐 사용했습니다.

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

2493번: 탑

이 문제를 응용해서 풀면 됩니다.

근데 문제 입출력에 오류가 있어서 맞았는지 틀렸는지는 모르겠어요.

정정 문자가 2번 왔는데 2번째 문자가 올 때까지 보느라 시간 다 버렸네요.

 

2번은 DP를 이용하여 풀려고 했습니다.

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

9251번: LCS

이 문제 푸는 방식을 이용하여 풀려고 했는데 시간이 모자라서 안 풀었습니다.

풀이 방법은 DP를 생각했는데 아닐 수도 있습니다. 1번 때문에 아쉽네요.

 

3번은 

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

6549번: 히스토그램에서 가장 큰 직사각형

이 문제입니다. 양심상 코드 복붙은 안 했습니다. 예전에 어려워 보여서 안 풀었던 기억이 있어서 아쉽네요.

 

4번은 리스트와 재귀를 이용했습니다.

트리의 자식 개수를 구하는 건데 각 노드의 부모를 저장하는 배열을 만들고 재귀를 돌려 모든 부모에 값을 더해줬습니다.

예를 들어 1-2-3으로 이어지는 skew tree가 있다고 가정하면 3의 부모인 2, 2의 부모인 1 모두 1씩 더해줬습니다.

그 후 값이 같은 것끼리 묶고 같은 값을 가지는 개수를 n(n-1)/2 해줘서 모두 더해줬습니다.

 

5번은 투 포인터 이용했습니다.

글자 수가 n이라고 했을 때 1~n까지 모든 글자에 대해 팰린드롬 검사를 했습니다.

글자 수가 1씩 증가하니 초기값에서 right는 고정하고 left가 right의 char와 같을 때까지 증가시켰습니다.

이후 left와 right의 char가 같으면 +2, left == right가 되면 +1 해줬습니다.

aabaa -> +2, +2, +1 이런 식으로요.

 

이 작업을 n번 반복해서 가장 큰 수를 출력했습니다.

 

4문제는 풀 수 있을 것 같았는데 시간상 아쉽게 됐습니다.

좋은 풀이가 있다면 공유해주세요. 너무 억지로 푼 것 같네요.