본문 바로가기

Problem Solving/SWEA147

[SWEA] 3143. 가장 빠른 문자열 타이핑 문제 어떤 문자열 A를 타이핑하려고 한다. 그냥 한 글자씩 타이핑 한다면 A의 길이만큼 키를 눌러야 할 것이다. 여기에 속도를 조금 더 높이기 위해 어떤 문자열 B가 저장되어 있어서 키를 한번 누른 것으로 B전체를 타이핑 할 수 있다. 이미 타이핑 한 문자를 지우는 것은 불가능하다. 예를 들어 A=”asakusa”, B=”sa”일 때, 다음 그림과 같이 B를 두 번 사용하면 5번 만에 A를 타이핑 할 수 있다. A와 B가 주어질 때 A 전체를 타이핑 하기 위해 키를 눌러야 하는 횟수의 최솟값을 구하여라. 풀이방법 n길이의 문자열 A와 m길이의 문자열 B가 주어진다. n길이의 A문자열을 0번째 인덱스부터 탐색을 할 때, 현재 탐색하고 있는 인덱스 i부터 i+m인덱스까지 문자가 B와 같다면 다음 탐색할 인덱.. 2020. 3. 11.
[SWEA] 2819. 격자판의 숫자 이어 붙이기 문제 4×4 크기의 격자판이 있다. 격자판의 각 격자칸에는 0부터 9 사이의 숫자가 적혀 있다. 격자판의 임의의 위치에서 시작해서, 동서남북 네 방향으로 인접한 격자로 총 여섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례대로 이어 붙이면 7자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 격자칸을 다시 거쳐도 되며, 0으로 시작하는 0102001과 같은 수를 만들 수도 있다. 단, 격자판을 벗어나는 이동은 가능하지 않다고 가정한다. 격자판이 주어졌을 때, 만들 수 있는 서로 다른 일곱 자리 수들의 개수를 구하는 프로그램을 작성하시오. 풀이방법 DFS(깊이 우선 탐색)알고리즘으로 문제를 해결 방문했던 노드를 재방문할 수 있는 길이가 7인 모든 경로를 구한다. 이 때 중복되는 숫자를 처리하는 방법은 0부.. 2020. 3. 11.
[SWEA] 5550. 나는 개구리로소이다 문제 개구리 한 마리가 한번 울면 “croak”하는 소리가 난다. 개구리 한 마리가 계속 여러 번 울면 울음소리가 다음처럼 나타날 수 있다. “croakcroak”, “croak”, “croakcroakcroakcroak” 영은이는 개구리를 연구하기 위해 많은 개구리를 사육한다. 영은이는 개구리들을 키우는 우리에 들어와 울음소리를 녹음했다. 여러 개구리가 동시에 울면 울음소리가 섞여서 녹음된다. 이 때 한 개구리의 울음소리는 녹음된 울음소리에서 부분 문자열로 나타난다. 이 부분 문자열은 연속하지 않아도 된다. 예를 들어 "crcoarkcoroakak"와 같을 수 있다. 그렇다면, 녹음을 할 때 있었던 개구리는 최소 몇 마리일까? 풀이방법 최소 개구리의 수를 구하기 위해서 다음과 같은 조건을 만족해야한다... 2020. 3. 11.
[SWEA] 1865. 동철이의 일 분배 문제 동철이가 차린 전자회사에는 N명의 직원이 있다. 그런데 어느 날 해야할 일이 N개가 생겼다. 동철이는 직원들에게 공평하게 일을 하나씩 배분하려고 한다. 직원들의 번호가 1부터 N까지 매겨져 있고, 해야 할 일에도 번호가 1부터 N까지 매겨져 있을 때, i번 직원이 j번 일을 하면 성공할 확률이 Pi, j이다. 여기서 우리는 동철이가 모든 일이 잘 풀리도록 도와주어야 한다. 직원들에게 해야 할 일을 하나씩 배분하는 방법은 여러 가지다. 우리는 여러 방법 중에서 생길 수 있는 “주어진 일이 모두 성공할 확률”의 최댓값을 구하는 프로그램을 작성해야 한다. 풀이방법 DFS(깊이 우선 탐색)알고리즘과 Backtracking(되추적)으로 해결한다. 모든 직원이 일이 중복 되지 않도록 일을 선택할 수 있는 모든.. 2020. 3. 10.
[SWEA] 7699. 수지의 수지 맞는 여행 문제 평소에 여행을 즐기는 수지는 이번에 새로운 섬에 도착했다. 이 섬은 1행, 1열로 시작해서 R행, C열까지 있으며, 총 R*C 칸으로 이루어져 있다. 수지는 지금 1행 1열에 있으며 앞으로 있을 야근을 위하여 기회 있을 때 미리 여행을 떠나려고 한다. 이 섬의 각 칸에는 알파벳이 적혀있다. 이 알파벳은 섬의 명물이고, 같은 알파벳은 같은 명물이다. 이 섬에서는 명물을 볼 때마다 요금을 지급해야 하는데 각 알파벳 명물을 처음 볼 땐 무료로 볼 수 있다. 그리고, 수지는 여행을 할 때 자신이 있는 지점의 명물을 본 후 4방향(상, 하, 좌, 우) 중 한 방향으로 1칸 이동 후 다음 명물을 보는 행동을 반복한다. 올해 SGA사 1년 차인 수지는 현재 대출빚과 카드빚에 허덕이고 있다. 따라서, 명물을 최대.. 2020. 3. 10.
[SWEA] 8659. GCD 문제 의석이는 종강 기념 피자 파티를 열기 위해서 피자를 사러 왔다. 하지만 피자 가게 주인 동욱이는 피자를 순순히 판매하지 않는 사람이다. 돈 보다 문제 내는 것을 더 좋아하는 이상한 동욱이는 피자를 사러 온 의석이에게 3개의 시련을 부여했고, 모두 통과해야만 거래를 시작한다. 두 번째 관문에서는 GCD에 관련된 내용을 물어본다. GCD(a,0) = a GCD(a,b) = GCD(b, a%b) GCD는 위와 같은 성질을 가진 함수이다. 동욱이가 원하는 것은 두 개의 숫자 A, B(A>B)를 찾는 것이다. 단, 이 두 개의 숫자에 대해서 GCD(A,B)를 실행하면 % 연산자가 총 K 번 수행된다는 사실을 알고 있다. 이러한 두 개의 숫자 조합 중에서 A가 가장 작으며 그런 조합이 여러 가지라면 B가 가장.. 2020. 3. 10.
[SWEA] 4050. 재관이의 대량 할인 문제 재관이의 옷 매장에서 대량 세일을 하고자 한다. 세일에는 조건이 한가지 있는데, 세 벌의 옷을 사면 그 중 가장 저렴한 한 벌에 해당하는 값은 내지 않아도 된다는 조건이다. 그리고 세 벌보다 많은 옷을 구매하는 경우에도 옷을 세 벌씩 나눠서 계산하면 같은 방식의 할인을 받을 수 있다. 예를 들면 10, 3, 2, 4, 6, 4, 9원짜리 옷을 사고자 할 때 (3, 2, 4), (10, 4, 9), (6)원짜리로 묶어서 계산을 하게 된다면, 첫 묶음에서 2원, 두 번째 묶음에서 4원 총 6원의 할인을 받게 되는 것이다. 다만 세 번째 묶음은 한 벌만 구매하므로 할인이 적용되지 않는다. 재관이네 매장에서 사고자 하는 옷이 있을 때 어떻게 묶어서 결제를 하면 가장 할인을 많이 받아서 구매를 할 수 있는지.. 2020. 3. 9.
[SWEA] 4261. 빠른 휴대전화 키패드 문제 동한이는 창고에서 오래된 애니콜 휴대전화를 발견했다. 이 휴대전화의 키패드는 아래와 같이 생겼다. 이 키패드는 각 키를 여러 번 눌러 영문을 입력할 수 있는데, a를 입력하려면 2를 한 번, b를 입력하려면 2를 두 번 누르는 식이다. 그러나 동한이는 이 방식이 너무 느리다고 생각하여 문자열을 빠르게 타이핑할 수 있도록 키패드를 다음과 같이 바꿔 보려고 한다. 사용할 단어들을 미리 휴대폰에 저장한 뒤, 해당 알파벳이 써있는 숫자를 한 번씩만 누르면 가능한 여러 단어 중에 사전에 저장된 단어를 찾아서 입력하는 것이다. 예를 들면 car를 입력하려면 222, 2, 777을 입력하는 것이 정상이지만 이 자판의 경우 227을 입력하면 aap, aaq, …, ccs 등 3×3×4=36개의 단어 중에 사전에 .. 2020. 3. 9.
[SWEA] 5432. 쇠막대기 자르기 문제 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.  - 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다.  - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.  - 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.  - 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다. 아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다. 이러한 레이저와 쇠막대기의 배치는 다.. 2020. 3. 9.
[SWEA] 1861. 정사각형 방 문제 N^2개의 방이 N×N형태로 늘어서 있다. 위에서 i번째 줄의 왼쪽에서 j번째 방에는 1이상 N2 이하의 수 Ai,j가 적혀 있으며, 이 숫자는 모든 방에 대해 서로 다르다. 당신이 어떤 방에 있다면, 상하좌우에 있는 다른 방으로 이동할 수 있다. 물론 이동하려는 방이 존재해야 하고, 이동하려는 방에 적힌 숫자가 현재 방에 적힌 숫자보다 정확히 1 더 커야 한다. 처음 어떤 수가 적힌 방에서 있어야 가장 많은 개수의 방을 이동할 수 있는지 구하는 프로그램을 작성하라. 풀이방법 DFS(깊이 우선 탐색)로 모든 경로를 찾는다. A[i][j] = x일 때, 상하좌우의 원소로 방문할 수 있는 경우는, 방문하려는 원소의 값이 x + 1이면서 방문한 적이 없어야한다. 위의 조건을 만족하는 모든 경로 중 경로의.. 2020. 3. 9.
[SWEA] 1258. [S/W 문제해결 응용] 7일차 - 행렬찾기 문제 유엔 화학 무기 조사단이 대량 살상 화학 무기를 만들기 위해 화학 물질들이 저장된 창고를 조사하게 되었다. 창고에는 화학 물질 용기 n2개가 n x n으로 배열되어 있었다. 유엔 조사단은 각 용기를 조사하여 2차원 배열에 그 정보를 저장하였다. 빈 용기에 해당하는 원소는 ‘0’으로 저장하고, 화학 물질이 들어 있는 용기에 해당하는 용기는 화학 물질의 종류에 따라 ‘1’에서 ‘9’사이의 정수를 저장하였다. 다음 그림은 창고의 화학 물질 현황을 9x9 배열에 저장한 예를 보여준다. 유엔 조사단은 화학 물질이 담긴 용기들로부터 3가지 사항을 발견하였다. 1. 화학 물질이 담긴 용기들이 사각형을 이루고 있다. 또한, 사각형 내부에는 빈 용기가 없다. 예를 들어, 위의 그림에는 3개의 화학 물질이 담긴 용기.. 2020. 3. 9.
[SWEA] 1233. [S/W 문제해결 기본] 9일차 - 사칙연산 유효성 검사 문제 사칙연산으로 구성되어 있는 식은 이진 트리로 표현할 수 있다. 아래는 식 “(8/2)*(6-4)”을 이진 트리로 표현한 것이다. 임의의 정점에 연산자가 있으면 해당 연산자의 왼쪽 서브 트리의 결과와 오른쪽 서브 트리의 결과를 사용해서 해당 연산자를 적용한다. 사칙연산 “+, -, *, /”와 양의 정수로만 구성된 임의의 이진 트리가 주어질 때, 이 식의 유효성을 검사하는 프로그램을 작성하여라. 여기서 말하는 유효성이란, 사칙연산 “+, -, *, /”와 양의 정수로 구성된 임의의 식이 적절한 식인지를 확인하는 것으로, 계산이 가능하다면 “1”, 계산이 불가능할 경우 “0”을 출력한다. (단, 계산이 가능한지가 아닌 유효성을 검사하는 문제이므로 0으로 나누는 경우는 고려하지 않는다. ) [제약 사항].. 2020. 3. 9.

티스토리툴바