삼성 대학생 프로그래밍 경진대회는 종 1차, 2차, 본선으로 이루어지며 대회 방식은 위와 같다.
나 또한 제 1회 삼성 대학생 프로그래밍 경진대회 (https://www.codeground.org)를 참여했었는데 대회 날과 그 다음날 약속이 있어서 몇문제 못 풀고 포기하였다.
통과되면 좋겠지만 평균도 못 미치는 점수이기에 기대를 접었다. -> 결과는 역시나 탈락
LG Code Challenger 2015(https://www.lgcodechallenger.com)는 10월 27일 9시부터 29일 9시 까지 이루어지는 대회이다.
이번이 두번째 대회이고 대상은 코딩을 좋아하는 학사이상(재/휴학생) 누구나(전공무관) 괜찮다고 한다.
시작일에는 조금 풀다가 이 대회또한 다른 약속이 생겨 포기할까 생각도 했다.
마음속으로는 이게 왜 코드문제야. 수학경시대회문제지 라는 생각이 들기도 하였다.
문제의 난이도와 별개로 개미굴 다시 짓기(3번문제)는 문제가 이해가 되지 않아 최소 20번은 읽은 듯 싶다.
하지만 2일이라는 시간은 약속이 생기더라도 이 대회를 끝까지 참여할 수 있게 하였고 그 결과 본선 진출 자격을 얻었다. 상품으로 주는 블루투스 이어폰이 끌리긴 했지만 본선은 포기했다..
두 대회는 문제 유형이 조금 달랐다.
우선 삼성 코드그라운드는 작은 데이터 입력을 풀 수 있는 방법은 쉽게 찾을 수 있었지만 큰 데이터를 풀 수 있는 방법을 찾기는 무척 어려웠다.
미련하게 한 문제를 풀겠다고 그것만 생각했는데 다시 되돌아간다면 우선 모든 문제를 풀 수 있는 답안을 다 찾은 뒤 코드를 고쳐나가 더 높은 점수를 노려보겠다.
또한 재귀호출은 자제해야할 것 같다.
대학교 시절 정균락 교수님께서 재귀호출은 좋지 않다고 하셨지만 코드의 간결함이 좋아 자주 쓰고 있었다.
하지만 이 대회에서 이 방식을 썼다가 계속 메모리와 시간 제한 오류가 떴다.
그림 : 삼성코드그라운드 1회 1번문제
엘지 코드 챌린저는 해결책만 찾으면 small.in과 large.in을 모두 쉽게 해결할 수 있었다.
삼성코드그라운드는 문제 해결시간이 2분이지만 엘지 코드 챌린저는 5분이 주어지기 때문이다.
또한 이 대회의 경우 컴퓨터의 성능이 매우 중요하다.
듀얼코어 컴퓨터에선 문제를 풀 수 없었는데 i7 컴퓨터에서는 시간안에 풀 수 있었다.
LG 코드 챌린저 1번 문제
직육면체의 대각
최근 블록쌓기 놀이에 푹 빠져있는 동현이를 위해 아버지인 철수는 변의 길이가 1인 정육면체 형태의 블록을 N개 사주었다. 동현이는 이 블록들을 이용하여 직육면체 형태를 만들기를 특히 좋아하였는데, 철수는 생각지도 못한 여러 가지 다른 크기와 형태의 직육면체를 만들기도 하였다.
<그림 1> 동현이가 만든 직육면체. 이 경우는 대각선의 길이가 정수가 아니다.
평소에도 수학에 관심이 있던 철수는 어느 날 동현이가 블록으로 만든 직육면체를 보다가 그 직육면체의 대각선의 길이가 정수가 된다는 걸 알아챘다. 직육면체의 대각선이란 직육면체의 꼭지점 중 가장 먼 둘을 이은 선을 말한다. 철수는 어떤 경우에 직육면체의 대각선의 길이가 정수가 되는지 알고 싶다.
한 변의 길이가 1인 정육면체 블록 N개 이하를 이용하여 만들 수 있는 직육면체 중에서 대각선의 길이가 정확히 정수가 되는 것들의 개수를 세는 프로그램을 작성하시오. 두 직육면체는 회전하였을 때 같아 보이거나 서로 거울상(mirror image)으로 보이면 같은 것으로 취급한다.
[입력] 입력 파일의 제일 첫째 줄에는 파일에 포함된 케이스의 수 T가 주어진다. 단 T ≤ 200이다.각 케이스의 첫째 줄에는 정육면체 블록의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다.
입력은 다음의 두 가지 종류로 주어진다.
- Small Set: 1 ≤ N ≤ 500
- Large Set: 1 ≤ N ≤ 10,000,000
[출력]
입력에 주어진 각 케이스에 대해 한 변의 길이가 1인 정육면체 블록 N개 이하를 이용하여 만들 수 있는 직육면체 중에서 대각선의 길이가 정확히 정수가 되는 것들의 개수를 정수 형태로 출력하시오.
[입출력 예]
- 입력
2
4
200
- 출력
1
11
LG 코드 챌린저 2번 문제
렌터카
대기업 영업사원인 K씨는 자기 소유의 차가 없기 때문에 차를 임대(rent)하여 사용한다. K씨가 거래하는 차량 임대회사는 두 곳이다. A사는 1일 단위로 차를 임대해 주는 회사이며, 임대하는 시간에 비례하여 임대료가 결정된다. 즉, A사로부터 차를 임대할 경우 시간당 임대료가 a원씩 부과된다. 반면, B사는 5일 단위로만 차를 임대해 주며, 차를 사용하는 시간에 상관없이 임대료는 5일에 b원이다. 만약 B사로부터 차량을 임대한 후 5일 이내에 차량을 반환해도 임대료는 역시 b원이다.
K씨는 매우 계획적으로 활동하기 때문에 앞으로 n일 동안 매일 몇 시간씩 차를 사용하는지에 대한 정보가 미리 주어져 있다. K씨의 차량 사용에 대한 정보. 그리고 임대료에 관한 정보 a와 b가 주어질 때, K씨가 차를 가장 저렴하게 사용할 수 있도록 도와 주는 프로그램을 작성하고자 한다.
예를 들어, a=1, b=50이고, 앞으로 8일 동안 K씨가 차량을 하루에 몇 시간씩 사용할지에 대한 정보가 ( 8, 11, 12, 13, 8, 9, 12, 7 )인 경우, 처음 이틀은 A사로부터, 3일째부터 7일째까지 5일간은 B사로부터, 마지막 8일 째는 A사로부터 차량을 임대하는 것이 가장 저렴하게 차량을 사용하는 일정이 된다. 그 때 임대 비용의 총액은 (8*a + 11*a + b + 7*a)=76이 된다.
[입력]
입력 파일의 첫째 줄에는 테스트 케이스를 나타내는 정수 T가 주어진다. 단 T ≤ 500이다. 각 케이스의 첫째 줄 세 정수 n, a, b가 주어진다. n(2 ≤ n ≤ 10,000)은 K씨가 차를 임대하길 원하는 날짜 수를 나타내며, a(1 ≤ a ≤ 100)는 A사로부터 차를 임대할 경우 시간 당 부과되는 임대료이며, b(1 ≤ b ≤ 10,000)는 B사로부터 차를 임대할 경우 5일당 부과되는 임대료이다. 참고로, 만약 B사로부터 차량을 임대한 후 5일 이내에 차량을 반환해도 임대료는 역시 b원이다. 이어 둘째 줄엔 n개의 수가 주어진다. n개의 각 수는 K씨가 차를 사용하는 시간을 나타내는 값으로써 0부터 24이하의 정수이다.
입력은 다음 두 가지 종류로 주어진다.
- Small set: 2 ≤ n ≤ 10
- Large set: 2 ≤ n ≤ 10,000
[출력]
입력에서 주어진 각 테스트 케이스에 대해 하나의 정수 값을 한 줄에 출력한다. K씨가 지불하는 차량 임대료의 총액이 가장 적게 되도록 차를 임대할 때, 그 때의 차량 임대료 총액을 출력한다.
[입출력 예]
- 입력
2
8 1 50
8 11 12 13 8 9 12 7
9 2 40
5 8 11 12 13 8 9 12 9
- 출력
76
80
LG 코드 챌린저 3번 문제
개미굴 다시 짓기
어떤 개미 집은 N개의 방과 그 방들을 연결하는 최대 N(N-1)/2 개의 복도들로 구성되어 있다. 각 복도는 두 개의 서로 다른 방을 연결하고, 한 쌍의 방 사이에는 최대 하나의 복도가 있다. 복도들은 서로 길이가 다를 수 있다. 매년 그렇듯이 올해도 홍수가 나서 집이 피해를 입었다. 이번에 입은 피해는 심각해서 집을 아예 다른 곳으로 옮길 수 밖에 없었다.
문제는 개미 집의 전체적인 구성을 기억하는 개미는 한 마리도 없다는 것이다, 다만 여왕 개미는 모든 쌍의 방들에 대해서 두 방 사이를 이동할 수 있는 최소 거리의 길에 대한 복도 길이 합을 알고 있다. 여왕 개미는 이전의 집에 애정이 많이 있어 똑 같은 집을 다시 만들고 싶지만, 그것은 불가능하므로 어쨌든 모든 쌍의 방들 간의 최소 이동 거리는 동일하게 만들려고 한다.
모든 방의 쌍들 간의 최소 거리를 입력으로 받아서, 그러한 거리를 만들 수 있는 개미집 중에서 모든 복도 길이의 합이 최소인 것을 계산하는 프로그램을 작성하라.
[입력]
입력 파일의 제일 첫째 줄에는 파일에 포함된 케이스의 수 T가 주어진다. 단, T ≤ 70이다. 각 케이스의 첫째 줄에 방의수를 나타내는 N이 자연수로 주어진다. 단, 2 ≤ N ≤ 500이다. 방은 1번부터 N번까지 번호가 붙어 있다. 이 후 N-1개의 줄 중 K 번째 줄에는 번호가 K인 방에서 번호가 각각 K+1, K+2,…, N인 N-K개의 방으로 가는 가장 짧은 길의 길이가 방 번호 순서대로 주어진다. 모든 거리 값은 1 이상 1,000이하의 자연수이다.
입력은 다음의 두 가지 종류로 주어진다.
- Small Set: 2 ≤ N ≤ 100
- Large Set: 2 ≤ N ≤ 500
[출력]
입력에 주어진 각 케이스에 대해 계산한 최소한의 개미 집에서 복도 길이의 합을 출력한다. 만약 불가능한 경우가 입력으로 주어졌다면 -1을 출력한다.
[입출력 예]
- 입력
2
3
2 3
3
4
1 1 2
2 2
4
- 출력
8
-1
LG 코드 챌린저 4번 문제
달표면
지질학을 연구하는 Octopus 교수는 달 표면의 토양을 분석하기 위해 달 표면의 사진 이미지에서 서로 다른 색을 갖는 픽셀들을 아래와 같이 분류하여 새로운 토양 사진을 만들려고 한다.
가로 N, 세로 M 픽셀 크기의 이미지에서 각 픽셀이 K개의 색들 가운데 한가지의 색으로 칠해져 있다. 이렇게 색이 칠해진 이미지 A를 분석해서 같은 크기의 이미지 B를 아래와 같이 만든다.
이미지 A의 i번째 행의 j번째 열에 해당하는 픽셀을 A(i,j)라고 할 때,
- 픽셀 B(i,j)는 이미지 A에서 픽셀 A(i,j)를 중심으로 좌,우,위,아래로 각각 R 픽셀 만큼 크기의 정사각형 (즉, 가로 2R+1, 세로 2R+1 픽셀 크기의 정사각형) 범위에 포함된 픽셀들에 칠해진 서로 다른 색들의 개수를 값으로 가진다.
- 이미지의 범위를 넘어서는 경우 해당 픽셀은 아무런 색도 칠해져 있지 않은 것으로 간주한다.
예를 들어, R이 1이라고 하면, B(i,j)는 A(i,j)를 중심으로 하는 9개의 픽셀들 A(i-1,j-1), A(i-1,j), A(i-1, j+1), A(i,j-1),A(i,j), A(i,j+1), A(i+1,j-1), A(i+1,j), A(i+1,j+1)에 칠해진 서로 다른 색들의 개수가 되고, R이 2라고 하면, B(i,j)는 A(i,j)를 중심으로 주변 25개의 픽셀들에 칠해진 서로 다른 색들의 개수가 된다.
가로 N, 세로 M 픽셀 크기 이미지가 주어졌을 때, 픽셀들에 사용된 색 정보를 주어진 R값에 따라 분석하여 같은 크기의 이미지 B를 위 규칙을 따라 만들어 출력하시오. 이미지 A에 모두 K개의 색들이 사용되었을 경우, 각각의 색은 K이하의 서로 다른 자연수로 표시된다.
[입력]
입력 파일의 제일 첫째 줄에는 파일에 포함된 케이스의 수 T가 주어진다. 단, T ≤ 160이다. 각 케이스의 첫째 줄에 이미지의 가로 크기 N(2 ≤ N ≤ 1,000)과 세로크기 M(2 ≤ M ≤ 1,000), 사용된 색의 개수 K(2 ≤ K ≤ 50), 정사각형의 범위 R(1 ≤ R ≤ 1,000)가 주어진다. 이 후 M개의 줄 각각에는 순서대로 N개의 픽셀들에 사용된 색이 주어진다. 각 픽셀의 색은 K이하의 자연수이다.
입력은 다음의 두 가지 종류로 주어진다.
- Small Set: 2 ≤ N ≤ 100, 2 ≤ M ≤ 100, 2 ≤ K ≤ 50, 1 ≤ R ≤ 100
- Large Set: 2 ≤ N ≤ 1,000, 2 ≤ M ≤ 1,000, 2 ≤ K ≤ 50, 1 ≤ R ≤ 1,000
[출력]
입력에 주어진 각 케이스에 대해 이미지 B의 모든 픽셀의 값을 더한 결과를 출력한다.
[입출력 예]
- 입력
2
4 4 5 1
1 2 1 2
2 4 2 3
5 4 2 1
1 2 3 1
6 5 8 2
1 2 4 3 2 7
3 4 3 4 3 2
8 6 3 4 2 4
5 3 6 8 7 4
1 5 4 7 8 4
- 출력
60
188
'일상 > 경진대회' 카테고리의 다른 글
| 임베디드 소프트웨어 경진대회 후기 (2015) (1) | 2015.11.26 |
|---|---|
| 임베디드 소프트웨어 경진대회 후기 (2014) (0) | 2014.12.10 |
