2023 SCON OpenContest

https://www.acmicpc.net/contest/view/999

2023 SCON Open Contest

 

대회 때는 4문제 밖에 풀지 못 했지만, 업솔빙을 했고, 총 7문제를 풀었다.

 

A -정보섬의 대중교통

단순 사칙연산 문제

b - n + n

 

소스코드

B - 팀명 정하기

단순 정렬문제

 

소스코드

 

C - 등차수열의 합

N = 1이면 무조건 가능하고,

N > 1이면 배열 안이 정확이 K만큼 증가한다면 무조건 가능하다.

출력해주는 방법은 다양한다.

 

소스코드

 

D - 선택 정렬의 이동 거리

구현 문제였다.

나같은 경우는 정렬과 맵 자료구조를 이용하여 정렬 전 상태와 정렬 후 상태를 비교하여 그 거리를 가지고 구현했다.

문제를 구현하다 꼬여가지고 시간을 날린게 컸다.

 

소스코드

 

여기까지가 대회 때 푼 문제들이고, 아래는 업솔빙을 했다.

 

E - prlong longf

DP 문제였다.

2가지 방법으로 풀었다.

첫 번째로

문자열을 받으면, 뒤에서 부터 시작해서 longlong가 있는지 체크하면서 전에 인덱스에서 longlong가 몇번 나왔는지 확인하면 된다. 이 방법같은 경우는 그 전에 longlong가 몇번나왔는지 따로 확인을 안 해도된다. 

 

두 번째로는

문자열을 받으면 앞에섣 부터 시작하는 방법인데, 이 방법같은 경우는 longlong가 나온 인덱스를 저장해줘야한다. 

그리고 longlong가 나온 인덱스에서는 dp[i - 1]에 자기가 나오기 전, longlong가 나온 인덱스의 dp값을 더해준다.

 

첫번째 방법 

소스코드.

두번째 방법

소스코드

F - 안전한 건설 계획

분리집합 문제였다.

문제만 보면 굉장히 어려워 보였다. 자세히 읽어보니 전형적인 Union-Find 문제였다.

결국 연결되있지 않은 그룹의 개수를 세워주면 된다.

입력받은 정점들을 Union해주고, 정점하나를 잡고, 자신과 다른 부모 노드를 가지고 있는 정점을 세워주면 된다.

 

소스코드

 

G - Traveling SCCC President

MST문제였다.

문제의 핵심은 "순간 이동 장치를 사용하면 지금까지 방문했던 건물 중 원하는 곳으로 순식간에 이동할 수 있다."

이 부분이다. 즉 방문을 했던 곳은 다시 갈필요가 없는 것이다.

그렇다면 결국 각 정점까지 가는데, 최단거리를 구하면 되는 것이기에 MST를 구하면 끝인 문제가 된다.

 

소스코드

 

G번까지가 내가 풀 수 있는 문제들이였다.

항상 대회를 하면 느끼는 것이지만, 나는 푸는 속도 느리다.

시간만 주면 어느정도의 난이도까지는 풀 수 있을 것같다.

하지만 대회에서는 시간도 촉박하고, 시간에 쫒기는 느낌을 받아 조급해져서 제대로 풀지 못 하는 것같다.

결국엔 내 실력이 문제이긴 하다.

졸작도 끝났고, 졸업요건 채울건 거의 다 채웠으니, 방학 때 문제 왕창 풀 것이다.

 

파이팅하자!!