본문 바로가기

Problem Solving/SWEA147

[SWEA] 7964. 부먹왕국의 차원 관문 문제 부먹 왕국은 찍먹 무리에게 침략을 당했었다. 하지만 탕수육의 힘으로 성공적으로 막아 내었으나 도시의 많은 차원관문이 파괴당했다. 부먹 왕국의 특징은 모든 도시들을 건설 할 때 일렬로 이어지게 만들었다. 어느 도시에 차원 관문을 설치하면 그 도시와 거리 D 이하인 다른 도시에서 차원 관문이 있는 곳으로 들어오거나, 혹은 차원 관문에서 거리 D 이하인 다른 도시로 나가는것이 가능하다. 찍먹 왕국의 재침공에 대비하기 위해서 모든 도시 이동이 되어야하며 모든 차원 관문 사이와 직접적으로 이동이 가능하도록 차원 관문을 재건하려고 한다. (단, 0번 위치와 N+1번 위치에는 차원 관문이 존재 한다.) 가능한 빠른 건설을 위하여 최소 개수로 설치하는 계획을 세우려고 할때 도시들마다 차원관문이 남아있는 지에 대한.. 2020. 2. 24.
[SWEA] 7728. 다양성 측정 문제 숫자는 다양성을 가지고 있다. 다양성이란, 숫자를 구성하는 수의 종류를 의미한다. 예를 들어서 1512 라는 숫자는 ‘1’, ‘5’, ‘2’로 구성되어 있기 때문에 다양성이 3이다. 숫자가 주어졌을 때 그 숫자의 다양성을 구하는 프로그램을 작성하라. 풀이방법 10크기의 1차원 배열을 선언하고 0으로 초기화 한다. 숫자가 입력으로 주워졌을 때, 각 자리 수의 값(0 ~ 9)와 일치하는 인덱스의 값에 1을 넣는다. 입력받은 숫자를 전부 검사했을 때, 배열 원소의 값 중 1의 값을 카운트한다. 소스코드 package samsung; import java.util.*; public class s_7728 { public static void main(String[] args) { Scanner sc = n.. 2020. 2. 24.
[SWEA] 7532. 세영이의 SEM력 연도 문제 세영이는 태양(S)과 지구(E)와 달(M)을 이용하여 연도를 기억한다. 이를 이용한 방법을 SEM력이라고 부르며, SEM력은 자연수 3개, S, E, M으로 이루어져있다. 첫 번째 수는 태양, 두 번째는 지구, 세 번째는 달과 관련 있다. AD 1년에 SEM력을 1 1 1로 정의했다. 1년이 지날 때마다 각 수를 1씩 증가시키는데, S는 365보다 커지면 1로, E는 24보다 커지면 1로, M은 29보다 커지면 1로 돌아온다. 예를 들어서 AD 24년은 24 24 24이고 AD 25년은 25 1 25이다. SEM력으로 이루어진 연도가 주어졌을 때, 이를 만족하는 실제 연도 중 가능한 가장 빠른 연도를 구하여라. 풀이방법 세 정수 S, E, M을 입력받았을 때, E가 가장 작은 수이므로 기준으로 잡는.. 2020. 2. 24.
[SWEA] 7510. 상원이의 연속 합 문제 연속적인 것에는 어떤 아름다움이 있다. 상원이는 자연수를 아름답게 쓰는 법을 고민하다가 연속된 자연수의 합으로 표현하기로 했다. 예를 들면, 15는 15 = 7 + 8 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5 로 4가지 방법이 있다. 아름다운 건 다다익선이라고 생각하는 상원이는 표현하고 싶은 자연수 N이 얼마나 많은 경우로 표현될 수 있는 지 궁금해졌다. 상원이를 도와서 문제를 해결하자. 풀이방법 n을 입력받았을 때 1부터 수를 증가 시켜 더해 n이 되는 수를 완전 탐색한다. 소스코드 package samsung; import java.util.*; public class s_7510 { public static void main(String[] args) { Scanner sc =.. 2020. 2. 24.
[SWEA] 6019. 기차 사이의 파리 문제 궁금증이 많은 한 소녀는 존 폰 노이만(John von Neumann)에게 다음과 같은 문제를 질문했다. “두 기차 A, B가 서로를 향해 달리고 있다. 두 기차의 전면부는 250마일 떨어져 있고 기차 A는 시속 10마일, B는 시속 15마일로 달리고 있다. 파리가 기차 A의 전면부에서 기차 B로 시속 20마일의 속력으로 날아간다. 파리가 기차 B의 전면부에 닿으면 바로 방향을 바꿔 기차 A를 향해 같은 속력으로 날아간다. 그러다 기차 A와 B가 충돌하면 파리는 죽을 것이다. 파리는 죽기 전 까지 몇 마일의 거리를 이동했을까?” 폰 노이만은 소녀의 질문에 대해 즉시 무한 급수를 이용해 답이 200마일이라는 것을 계산해냈다. 소녀가 질문한 문제의 조금 더 일반화된 버전을 해결해보자. 풀이방법 1) 파.. 2020. 2. 24.
[SWEA] 4789. 성공적인 공연 기획 문제 동욱이는 공연을 기획하고 있다. 이번이 그가 처음으로 기획한 공연이기 때문에, 성공에 매우 민감하여 반드시 공연을 성공시키겠다는 집념으로 불타고 있다. 동욱이는 이런 집착 중 하나로 공연이 끝난 후 모든 사람들의 기립 박수를 받고 싶다. 사람들은 공연이 끝난 후 모두 기립 박수를 할 생각이 있지만 기립 박수를 시작하는 타이밍은 사람마다 다를 수 있다. 이는 사람들이 가진 각자의 부끄러움 때문인데, 지금 기립 박수를 하고 있는 사람의 수가 특정한 수 이상이 되면 그제서야 일어나서 기립 박수를 하게 되는 것이다. 이 특정한 수를 넘지 않으면 절대로 기립 박수를 하지 않는다. 그렇기에 우선 아무런 조건이 없이 기립 박수를 하는 사람들이 기립 박수를 시작하고, 그것을 본 다른 사람들이 또 일어나서 연쇄적으.. 2020. 2. 24.
[SWEA] 4371. 항구에 들어오는 배 문제 민석이는 항구가 있는 작은 마을에 산다. 이 항구에는 배가 아주 드물게 지나다닌다. 민석이는 어느날 모든 배들이 항구에 들어온 것을 보았다. 민석이는 이 날을 1일차로 지정하였다. 민석이는 배가 한 척이라도 항구에 들렀던 날을 “즐거운 날"로 이름짓고, 1일차부터 즐거운 날들을 모두 기록하였다. 그러던 중, 한 가지 규칙을 발견했는데, 그 규칙은 각 배들은 항구에 주기적으로 들른다는 것이었다. 예를 들어, 주기가 3인 배는 항구에 1일차, 4일차, 7일차, 10일차 등에 방문하게 된다. 민석이가 1일차부터 기록한 “즐거운 날"들의 목록이 주어질 때, 항구에 들렀던 배의 최소 수를 알아내자. 이 때, 항상 답이 존재하는 입력만 주어진다. 풀이방법 오름차순으로 입력되는 수는 등차(d1, d2, d3, .. 2020. 2. 24.
[SWEA] 2817. 부분 수열의 합 문제 A1, A2, ... , AN의 N개의 자연수가 주어졌을 때, 최소 1개 이상의 수를 선택하여 그 합이 K가 되는 경우의 수를 구하는 프로그램을 작성하시오. 풀이방법 DFS(깊이 우선 탐색)로 공집합을 제외한 모든 부분집합을 구하고 부분집합의 합이 k와 일치하는 계수를 구한다. 소스코드 package samsung; import java.util.*; public class s_2817 { static int n; static int k; static int[] a; static int[] visit; static int cnt; public static void dfs(int x, int sum) { visit[x] = 1; sum += a[x]; if(sum == k) cnt++; for(int.. 2020. 2. 23.
[SWEA] 7102. 준홍이의 카드놀이 문제 각 카드 세트는 1번 카드부터 N번 카드, 1번 카드부터 M번 카드로 구성되어 있다. N번 카드와 M번 카드를 각 카드를 한장 씩 골라 두 카드의 합을 구한다. 각 카드 세트에서 카드를 한 장씩 골라서 카드에 적힌 숫자를 합한 결과 중, 등장할 확률이 가장 높은 숫자는 어떤 숫자인지 구하라. 풀이방법 완전탐색으로 N과 M카드로 나올 수 있는 모든 값을 구한다. 이 때, N + M + 1 크기의 배열을 만들어 합과 일치하는 인덱스의 값을 계속해서 증가시킨다. 배열의 각 원소가 최댓값인 인덱스를 찾는다. 소스코드 package samsung; import java.util.*; public class s_7102 { public static void main(String[] args) { Scanner.. 2020. 2. 23.
[SWEA] 7087. 문제 제목 붙이기 문제 은기는 대회의 문제들에 사용할 수 있는 제목을 N개 만들었다. 자영이는 제목의 가장 앞 글자에 알파벳 대문자 A부터 시작하여, A, B, C, … , Z가 순서대로 한 번씩 등장하면 좋겠다고 하였다. 만약 도중에 특정 알파벳이 문제 제목의 맨 앞 글자로 등장하지 않으면 그 이후의 알파벳은 사용하지 않는다. 예를 들어, 문제 제목으로 Air, Dad, Ear, Blue, Ace가 있다면, A와 B는 등장하였지만, C는 등장하지 않았기 때문에 최대 2개의 문제 제목을 사용할 수 있는 것이다. 은기가 만든 문제들의 제목이 주어질 때, 자영이가 정한 규칙에 따라서 사용할 수 있는 최대 문제 제목의 개수를 계산하는 프로그램을 작성하라. 풀이방법 알파벳 대문자 갯수 크기의 배열을 선언하고 0으로 초기화한다. .. 2020. 2. 23.
[SWEA] 6913. 동철이의 프로그래밍 대회 문제 N명의 사람들이 어떤 프로그래밍 대회에 참가했고, 대회에는 M개의 문제가 나왔다. NⅹM 크기의 2차원 배열 a가 주어질 때, ai,j 는 대회가 끝나고 i번 사람이 j번 문제를 풀었다면 1, 풀지 못했다면 0을 가지는 값이다. 2차원 배열을 보고 1등을 한 사람이 몇 명이고 몇 문제를 풀었는지 구하는 프로그램을 작성하라. 풀이방법 입력된 2차원 배열의 각 행의 합 중 최대값을 구하고, 이 최대값과 같은 값을 가지는 행의 갯수를 구한다. 소스코드 package samsung; import java.util.*; public class s_6913 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int te.. 2020. 2. 23.
[SWEA] 6730. 장애물 경주 난이도 문제 참가자들은 가장 처음 블록 위에서 가장 마지막 블록의 위로 이동해야 한다. 주어진 장애물에서 올라갈 때의 높이 변화와 내려갈 때의 높이 변화 둘 각각에 대해 가장 높이 변화가 심한 부분을 난이도라 하기로 했다. 장애물들이 주어질 때, 올라갈 때와 내려갈 때의 난이도를 출력하는 문제. 풀이방법 각 장애물에서 다음 장애물과의 차를 구한다. 이 때, 차가 양수이면 올라가는 경우이고, 음수이면 내려가는 경우이다. 올라가는 경우와 내려가는 경우 각각의 최댓값을 구한다. 소스코드 package samsung; import java.util.*; public class s_6730 { public static void main(String[] args) { Scanner sc = new Scanner(Syste.. 2020. 2. 23.

티스토리툴바