본문 바로가기

Problem Solving/SWEA147

[SWEA] 9229. 한빈이와 Spot Mart 문제 한빈이는 퇴근길에 스팟마트에 들러 과자 두 봉지를 사서 양 손에 하나씩 들고 가려고 한다. 스팟마트에는 N개의 과자 봉지가 있으며, 각 과자 봉지는 ai그램의 무게를 가진다. 배가 많이 고픈 한빈이는 최대한 양이 많은 (무게가 많이 나가는) 과자 봉지를 고르고 싶으나, 과자 두 봉지의 무게가 M 그램을 초과하면 무거워서 과자를 들고 다닐 수 없다. 한빈이가 들고 다닐수 있는 과자들의 최대 무게 합을 출력하라. 한빈이는 과자를 “정확히” 두 봉지 사야 함에 유의하라. 풀이방법 한빈이가 가져갈 수 있는 경우의 수를 모두 찾고 이 중 M을 넘지 않는 최대값을 출력한다. 한빈이가 가져갈 과자는 2 봉지이므로 DFS(깊이우선탐색)을 사용하지 않아도 이중 반복문으로 구할 수 있다. 소스코드 package sa.. 2020. 2. 25.
[SWEA] 8931. 제로 문제 재현이는 재민이를 도와서 동아리 장부를 관리하고 있다. 재현이는 영수증을 모아서 동아리의 지출 금액을 세고 있고, 재민이는 재현이가 부르는 액수를 순서대로 적고 있다. 재현이는 가끔 잘못된 수를 부르는 실수를 하는데, 이 때마다 0을 외쳐서, 가장 최근에 재민이가 쓰고 지우지 않았던 수를 지우게 시킨다. 재현이가 모든 수를 부른 후 재민이가 받아 적은 수의 합은 무엇일까? 풀이방법 스택(Stack) 자료구조의 후입선출(LIFO, Last In First Out)을 이용한다. 재현이가 말하는 숫자를 스택에 집어넣되, 재현이가 0을 말하면 스택에 가장 최근에 입력된 값을 삭제한다. 소스코드 package samsung; import java.util.*; public class s_8931 { publ.. 2020. 2. 25.
[SWEA] 8821. 적고 지우기 문제 진수는 어린 동욱이에게 숫자 공부를 시키고 있다. 진수는 숫자를 여러 번 말한다. 그러면 동욱이는 진수가 부르는 숫자를 공책에 적거나 지운다. 숫자를 적을 때는 공책에 그 숫자가 적혀 있지 않을 때이고, 숫자를 지울 때는 공책에 그 숫자가 적혀 있을 때이다. 처음 공책에는 어떤 숫자도 적혀 있지 않다고 할 때, 마지막에 공책에 적힌 숫자의 개수를 구하는 프로그램을 작성하라. 풀이방법 동욱이가 부르는 숫자는 0 ~ 9 사이이다. 10 크기의 1차원 배열을 선언하고 0으로 초기화한다. 동욱이가 말하는 수와 같은 인덱스의 원소가 0이면 1, 1이면 0으로 대입해가며 동욱이가 말하는 일련의 숫자를 읽는다. 소스코드 package samsung; import java.util.*; public class s.. 2020. 2. 25.
[SWEA] 8741. 두문자어 문제 이번 여름 휴가로 하와이를 갈 예정인 상길이는 매일 영어 단어를 외운다. 똑똑한 상길이는 이전에 외운 단어는 단어의 앞글자만 보면 다시 기억해낼 수 있다. 상길이는 자신이 외운 영어 단어를 까먹을 때를 대비해서 단어의 앞글자를 따와 대문자로 적어 놓으려고 한다. 상길이를 도와 세 단어의 앞글자를 따와서 대문자로 바꾸는 프로그램을 작성해보자. 예를 들어 “knuth morris pratt”은 “KMP”로 바뀐다. 풀이방법 입력받은 각 문자열의 맨 앞글자를 대문자로 바꾸어 출력 소스코드 package samsung; import java.util.*; public class s_8741 { public static void main(String[] args) { Scanner sc = new Scann.. 2020. 2. 25.
[SWEA] 8658. Summation 문제 의석이는 종강 기념 피자 파티를 열기 위해서 피자를 사러 왔다. 하지만 피자 가게 주인 동욱이는 피자를 순순히 판매하지 않는 사람이다. 돈 보다 문제 내는 것을 더 좋아하는 이상한 동욱이는 피자를 사러 온 의석이에게 3개의 시련을 부여했고, 모두 통과해야만 거래를 시작한다. 첫 번째 관문에서는 10개의 자연수가 주어진다. 각 수마다 그 수의 각 자리 수를 다 더한 값을 계산해야 한다. 예를 들어서 주어진 수 중에 1203이 있다면 이 수의 각 자리 수를 모두 더하면 1 + 2 + 0 + 3 = 6이 된다. 의석이는 동욱이에게 받은 10개의 숫자들 중, 위와 같이 변환했을 때의 최대, 최소값을 대답해야만 한다. 의석이를 도와서 관문 1의 정답을 구하는 프로그램을 작성하라. 풀이방법 완전탐색으로 10개.. 2020. 2. 25.
[SWEA] 6808. 규영이와 인영이의 카드게임 문제 규영이와 인영이는 1에서 18까지의 수가 적힌 18장의 카드로 게임을 하고 있다. 한 번의 게임에 둘은 카드를 잘 섞어 9장씩 카드를 나눈다. 그리고 아홉 라운드에 걸쳐 게임을 진행한다. 한 라운드에는 한 장씩 카드를 낸 다음 두 사람이 낸 카드에 적힌 수를 비교해서 점수를 계산한다. 높은 수가 적힌 카드를 낸 사람은 두 카드에 적힌 수의 합만큼 점수를 얻고, 낮은 수가 적힌 카드를 낸 사람은 아무런 점수도 얻을 수 없다. 이렇게 아홉 라운드를 끝내고 총점을 따졌을 때, 총점이 더 높은 사람이 이 게임의 승자가 된다. 두 사람의 총점이 같으면 무승부이다. 이번 게임에 규영이가 받은 9장의 카드에 적힌 수가 주어진다. 규영이가 내는 카드의 순서를 고정하면, 인영이가 어떻게 카드를 내는지에 따른 9!가.. 2020. 2. 24.
[SWEA] 6485. 삼성시의 버스 노선 문제 삼성시에 있는 5,000개의 버스 정류장은 관리의 편의를 위해 1에서 5,000까지 번호가 붙어 있다. 그리고 버스 노선은 N개가 있는데, i번째 버스 노선은 번호가 Ai이상이고, Bi이하인 모든 정류장만을 다니는 버스 노선이다. P개의 버스 정류장에 대해 각 정류장에 몇 개의 버스 노선이 다니는지 구하는 프로그램을 작성하라. 풀이방법 정류장 수만큼의 배열을 선언하고 0으로 초기화한다. n줄에 걸쳐 ai와 bi가 입력되면 ai이상 bi이하의 정류장을 다니는 노선이 있다는 의미이므로 ai이상 bi이하의 배열 인덱스의 원소 값을 1증가 시켜준다. 그런다음 p개의 정류장을 입력받고 해당하는 정류장의 노선 개수(인덱스의 원소값)를 출력해준다. 소스코드 package samsung; import java.u.. 2020. 2. 24.
[SWEA] 3233. 정삼각형 분할 놀이 문제 한 변의 길이가 A인 정삼각형의 내부를 한 변의 길이가 B인 정삼각형으로 나누려고 한다. 이 때 필요한 한 변의 길이가 B인 정삼각형의 최소 개수를 구하는 프로그램을 작성하라. B는 A의 약수이다. A = 2, B = 1 일 때의 한 변의 길이가 B인 정삼각형의 최소 개수는 아래 그림과 같다. 풀이방법 A의 면적 / B의 면적 소스코드 package samsung; import java.util.*; public class s_3233 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int tc = sc.nextInt(); for(int t = 1; t 2020. 2. 24.
[SWEA] 3376. 파도반 수열 문제 아래 그림과 같이 삼각형이 나선모양으로 늘어서 있는 형태를 생각해보자. 아래 그림과 같이 삼각형이 나선모양으로 늘어서 있는 처음에 이 나선은 한 변의 길이가 1인 정삼각형에서 시작한다. 그리고 현재 만들어진 나선에서 가장 긴 변에 그 변의 길이와 같은 크기의 정삼각형을 추가해 넣는다. 파도반 수열 PN은 나선에 N번째로 추가한 나선의 길이를 의미하는 수열이다. P1에서 P10까지를 순서대로 나열하면 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어질 때 PN을 구하는 프로그램을 작성하라. 풀이방법 파도반 수열은 대표적인 동적 계획(DP, Dynamic Programming) 알고리즘으로 해결할 수 있는 문제이다. 문제에 주어진 값으로 점화식을 세우면 D[n] = D[n-1] + D.. 2020. 2. 24.
[SWEA] [S/W 문제해결 응용] 2일차 - 최대 상금 문제 퀴즈 대회에 참가해서 우승을 하게 되면 보너스 상금을 획득할 수 있는 기회를 부여받는다. 우승자는 주어진 숫자판들 중에 두 개를 선택에서 정해진 횟수만큼 서로의 자리를 위치를 교환할 수 있다. 예를 들어, 다음 그림과 3, 2, 8, 8, 8 의 5개의 숫자판들이 주어지고 교환 횟수는 2회라고 하자. 교환전> 처음에는 첫번째 숫자판의 3과 네 번째 숫자판의 8을 교환해서 8, 2, 8, 3, 8이 되었다. 다음으로, 두 번째 숫자판 2와 마지막에 있는 8을 교환해서 8, 8, 8, 3, 2이 되었다. 정해진 횟수만큼 교환이 끝나면 숫자판의 위치에 부여된 가중치에 의해 상금이 계산된다. 숫자판의 오른쪽 끝에서부터 1원이고 왼쪽으로 한자리씩 갈수록 10의 배수만큼 커진다. 위의 예에서와 같이 최종적으로.. 2020. 2. 24.
[SWEA] 8500. 극장 좌석 문제 좌석이 일렬로 나열된 극장에 N명의 사람이 앉아있다. i번 사람의 왼쪽과 오른쪽으로 적어도 Ai개의 좌석이 연속해서 비어 있다. 즉, i번 사람은 2Ai개의 좌석이 비어 있는 것을 아는 것이다. 이 때, 극장의 좌석 개수로 가능한 수의 최소값을 구하는 프로그램을 작성하라. 사람들은 번호 순서대로 극장에 앉아 있는 것이 아님에 유의하라. 풀이방법 입력으로 2 3 2가 주어졌다는 말은 좌우에 빈좌석을 2개 필요로하는 사람, 3개 필요로하는 사람, 2개 필요로하는 사람이 있다는 의미. 문제에서 입력은 사람들이 앉은 순서대로 주어지지않았다는 점과 좌석의 최소한의 개수를 구하라고 했으므로 그리디 알고리즘으로 해결가능하다. 먼저 입력받은 수를 오름차순으로 정렬하고 앉은 사람의 사이마다 최소한의 좌석을 둔다. .. 2020. 2. 24.
[SWEA] 8104. 조 만들기 문제 삼성대학교 프로그래밍 기초 과목에서 조별과제를 위해 N명으로 구성된 조를 K개 만들고자 한다. 프로그래밍 과목의 수강 인원은 정확히 N × K명이기 때문에, 완벽하게 조를 구성하는 것이 가능하다. 조에 들어가는 사람들의 실력을 최대한 균등하게 하기 위해 이미 치른 중간고사 성적을 이용한다. 성적은 모든 학생들이 달랐기 때문에, 1등에서 N × K등의 학생이 정해져 있다. 각 조에 1번에서 K번까지의 번호를 붙인 다음과 같이 K개의 조를 구성한다. - 1등에서 K등인 학생은 순서대로 1번 조에서 K번 조까지 들어간다. - K+1등에서 2K등인 학생은 역순으로 1번 조에서 K번 조까지 들어간다. - 2K+1등에서 3K등인 학생은 순서대로 1번 조에서 K번 조까지 들어간다. - … 예를 들어, N = 1.. 2020. 2. 24.

티스토리툴바