CodeDrive

문제:

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.

행렬을 변환하는 연산은 어떤 3*3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 -> 1,1 -> 0)

입력:

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.

출력:

첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.

풀이방법:

 그리디 방법이므로 현재 위치하고 있는 곳에서 A와 B를 비교해서 뒤집을지 결정해주면 된다. 왼쪽 위부터 오른쪽으로 한칸씩 미끄러져 가며 비교를 하고 맨 윗줄을 다 비교하면 그 아랫줄로 내려가서 비교를 해주도록 한다. 이렇게 하면 한 번 그 위치를 기준으로 뒤집은 경우에는 다시 그 칸을 뒤집진 않기 때문에 한 번 뒤집었던 부분을 다시 뒤집을 수 있다는 걱정을 할 필요 없다. 따라서 이렇게 행렬A를 탐색하며 다 뒤집은 다음에 행렬 B와 비교해서 일치한다면 연산의 최솟값을 출력하고 그렇지 않다면 -1을 출력하도록 하였다.

문제 링크:

https://www.acmicpc.net/problem/1080

문제:

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이라는 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.

미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.

입력:

N을 입력받는다. N은 최대 10^5개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.

출력:

미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.

풀이방법:

 30의 배수가 되기 위해서는 10의 배수의 특징과 3의 배수 특징을 모두 가지고 있어야 한다. 10의 배수가 되려면 자릿수의 맨 끝이 0이 되어야 한다. 3의 배수가 되려면 각 자리를 다 더했을 때 3의 배수가 되어야 한다. 따라서 숫자에 0이 존재하고 각 자리를 모두 합했을 때 3의 배수라면 30의 배수를 만들 수 있다.

 따라서 30의 배수중 가장 큰 수를 원하기 때문에 각 자리를 리스트의 원소로 가지고 있는 배열을 역순으로(내림차순으로) 정렬한 뒤에 붙이는 것이 가장 큰 값이 될 것이다.

문제링크:

https://www.acmicpc.net/problem/10610

문제:

백준대학교에는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다.(왜인지는 총장님께 여쭈어보는 것이 좋겠다.)

백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다.

그런데 올해에는 대회에 참여하라는 학생들 중 K명을 반드시 인턴쉽 프로그램에 참여하라는 학교의 방침이 생기게 되었다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다.

입력:

첫째 줄에 N,M,K가 순서대로 주어진다 (0<=M<=100),(0<=N<=100),()<=K<=M+N)

출력:

만들 수 있는 팀의 최댓값을 출력하면 된다.

풀이 방법:

 인턴쉽에 K명이 반드시 참가해야하므로 이 인원을 먼저 빼도록 한다. 따라서 현재 남자와 여자 인원이 있을 때 만들 수 있는 팀이 있을 때 남는 인원들을 한명씩 인턴쉽으로 빼도록 한다. 이렇게 모두 인턴쉽에 K명을 모두 배정하고 난 뒤에 남은 사람들로 팀의 수를 출력하도록 한다.

문제 링크:

https://www.acmicpc.net/problem/2875

문제:

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)을 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

예를 들면, 어떤 수열이 {0,1,2,4,3,5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 =15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야 한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

입력:

첫째 줄에 수열의 크기 N이 주어진다. N은 10,000보다 작다. 둘째 줄부터 N개의 줄에, 수열에 각 수가 주어진다. 수열의 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

출력:

수를 적절히 묶어 그 합이 최댓값을 출력한다. 정답은 항상 2^31보다 작다.

풀이 방법:

 합이 최댓값이 되도록 만들기 위해서는 양수는 양수끼리 곱해야 하고, 음수는 음수와 곱해서 양수가 되도록 만들어야 한다. 또한 작은 수와 곱하기 보다는 절대값이 큰 값들끼리 묶어야 합이 최댓값이 될 것이다. 따라서 수를 받을 때 양수와 음수로 나누어서 받도록 한다.

 그리고 값 중에서 1과 0은 최댓값으로 만들 때 방해가 되는 항목들이다. 0과 함께 묶으면 그 값은 0이 되어버려 사용할 수 없게 된다. 따라서 이는 음수가 홀수일 때 사용하도록 한다. 또한 1도 양수와 곱해졌을 때 손해가 되는 항목이다. (4*1<4+1) 묶지 않고 그냥 더하는 것이 크기 때문이다. 그래서 이 둘의 항목은 따로 셈을 해주도록 한다,

 양수와 음수로 분리를 하고 난 뒤에 음수는 오름차순, 양수는 내림차순으로 정렬해서 곱을 편하게 만들었다. 또한 이들의 개수가 홀수이면 예외처리를 따로 해줘야 하는 번거로움이 생기기 때문에 임의의 값인 1이나 0을 넣어주도록 했다. 

 이러한 사전작업이 끝난다면 두 값씩 묶은 뒤에 더해주도록 했다.

문제 링크:

https://www.acmicpc.net/problem/1744

문제:

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 시간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N=7인 경우에 다음과 같은 상담 일정표를 보자.

 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3,4,5,6 일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6,7이렝 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이 때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1<=N<=15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1<=Ti<=5,1<=Pi<=1,000)

출력:

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

풀이방법:

기간을 넘어가서 상담을 할 수는 없는 것이므로 뒤에서 부터 값을 업데이트 하며 오도록 하였다. i일의 최대 가능한 금액은 이전의 값을 그대로 가져오가나 몇일 지난 값을 더한 값이 되게 된다. 따라서 이 점화식에 따라서 계속해서 값을 구하다 보면 d[0]에 최대값이 담기게 된다.

문제링크:

https://www.acmicpc.net/problem/14501

문제:

영어에서는 어떤 글자가 다른 글자보다 많이 쓰인다. 예를 들어, 긴 글에서 약 12.31% 글자는 e이다.

어떤 글이 주어졌을 때, 가장 많이 나온 글자를 프로그램을 작성하시오.

입력:

첫째 줄부터 글의 문장이 주어진다. 글은 최대 5000글자로 구성되어 있고, 공백, 알파벳 소문자, 엔터로만 이루어져 있다 그리고 적어도 하나의 알파벳이 있다.

출력:

첫째 줄에 가장 많이 나온 문자를 출력한다. 여러 개일 경우에는 알파벳 순으로 앞서는 것부터 모두 공백없이 출력한다.

풀이방법:

 알파벳의 개수를 세는 크기가 26인 배열을 만들어서 해당하는 알파벳을 만날 때마다 해당하는 인덱스에 +1을 하도록 한다.( 예를 들면 a를 만나면 인덱스 0의 값을 +1한다.) 이렇게 모든 글을 탐색하고 난 뒤에 알파벳 배열의 max값과 일치하는 값들을 출력하도록 하게 한다.

문제링크:

https://www.acmicpc.net/problem/1371

문제:

 창영이는 민균이의 컴퓨터를 해킹해 텍스트 파일 하나를 자신의 메일로 전송했다. 파일에는 단어가 한 줄에 하나씩 적혀있었고, 이 중 하나는 민균이가 온라인 저지에서 사용하는 비밀번호이다.

파일을 살펴보던 창영이는 모든 단어의 길이가 홀수라는 사실을 알아내었다. 그리고 언젠가 민균이가 이 목록에 대해서 얘기했던 것을 생각해냈다. 민균이의 비밀번호는 목록에 포함되어 있으며, 비밀번호를 뒤집어서 쓴 문자열도 포함되어 있다.

예를 들어, 민균이의 비밀번호가 "tulipan"인 경우에 목록에는 "napilut"도 존재해야 한다. 알 수 없는 이유에 의해 모두 비밀번호로 사용 가능하다고 한다.

민균이의 파일에 적혀있는 단어가 모두 주어졌을 때, 비밀번호의 길이와 가운데 글자를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 단어의 수 N(2<=N<=100)이 주어진다. 다음 N개의 줄에는 파일에 적혀있는 단어가 한 줄에 하나씩 주어진다.

단어는 알파벳 소문자로만 이루어져 있으며, 길이는 2보다 크고 14보다 작은 홀수이다.

출력:

첫째 줄에 비밀번호의 길이와 가운데 글자를 출력한다. 항상 답이 유일한 경우만 입력으로 주어진다.

풀이방법:

 처음 단어를 받을때 원래 단어와 뒤집은 단어 두개씩 넣도록 하였다. 이렇게 한다면 비밀번호인 단어는 words라는 배열에 두 개씩 담기게 될 것이다.

 그리고 이 words라는 배열에 set을 취하게 되면 중복인 것들이 사라지게 되고, words에 set을 한번 한 배열을 빼면 비밀번호인 문자만 남게 될 것이다. 항상 홀수 길이의 단어이므로 둘 중 어느것의 가운데 글자를 출력해도 상관없으니 아무 것이나 선택해서 출력하도록 했다.

문제링크:

https://www.acmicpc.net/problem/9933

문제:

N x M 크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1,1)에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

입력:

첫째 줄에 두 정수 N,M(2<=N,M<=100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력:

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

풀이방법:

 최소의 칸 수를 구해야 하는 문제에서는 DFS가 적합하지 않은 경우가 많다. 따라서 이 문제는 BFS를 사용해서 풀어야 하는 문제다.

BFS(queue)를 사용해서 1이 있는 위치에다가 check에 거리를 할당하며 (1,1)에서 (N,M)으로 가도록 하면 된다. 예제 입력2를 통해 설명하면 다음과 같다.

초기 check 배열은 다음과 같이 모두 0이며 (1,1)에서 출발해야 하므로 0,0은 1으로 할당해두도록 한다. 또한 (1,1)를 queue에 넣어두도록 한다.

queue에서 (1,1)을 빼고 이 값을 기준으로 (1,2)와(2,1)가 1로 이동할 수 있으므로 2로 할당한다. 이 값들을 queue에 넣어준다.

(1,2)와 (2,1)를 빼고 이 값에서는 (2,2),(1,3)이 이동 가능하므로 3으로 할당하고 이 값들을 queue에 넣어준다.

따라서 이 방식대로 계속해서 queue에서 빼고, 넣는 작업을 반복한다

count=5일 때,

count=6일 때,

count=7일 때,

count=8일 때,

count=9일 때,

이렇게 계속하다보면 더 이상 queue에 남아 있는 값이 없게 되는데 이 것이 탐색의 끝을 의미한다. 따라서 탐색을 마치고 난 뒤에 (n,m) 값이 정답이다.

문제링크:

https://www.acmicpc.net/problem/2178

문제:

<그림1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림2>는 <그림1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력:

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5<=N<=25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0 혹은 1)가 입력된다.

출력:

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

풀이방법:

 이 문제는 크게 두 부분으로 나누어서 풀어야 한다. check에 <그림2>와 같이 배열을 만드는 부분, 그리고 <그림2>를 탐색하며 각 단지번호의 갯수를 세는 부분으로 나누어서 풀었다.

 첫 부분은 dfs를 사용해서 값을 할당했다. <그림1>의 배열을 탐색하면서 값이 1이고 check가 아직 0인(방문을 하지 않은) 값을 만나면 그 값으로부터 dfs를 시작하도록 한다. check에 count 값을 할당하면서 다음 dfs 값으로 이동하였다. 이 때 상하좌우로 이동할 수 있었는데 깔끔하게 이동할 수 있도록 dx와 dy라는 배열을 만들어서 하나의 반복문으로 이동을 간단하게 만들었다.

 이렇게 한 단지를 다 탐색하고 나면 다시 처음상태로 돌아가서 다시 값이 1이고 check가 0인 곳을 찾고, 위와 동일하게 check에 count에 1이 증가한 값들을 할당해주면 된다.

 <그림1>을 모두 탐색하고 난다면 check에 <그림2>와 같이 지도를 얻을 수 있다. 그러면 이 check를 count의 갯수만큼 탐색하며 단지번호의 갯수를 세도록 한다.

문제링크:

https://www.acmicpc.net/problem/2667

문제:

다음과 같이 정의된 수열이 있다.

• D[1] = A
• D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합

예를 들어 A=57, P=2일 때, 수열 D는 {57, 74(=5^2+7^2=25+49),65,61,37,58,89,145,42,20,4,16,37, ...}이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다.

이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 {57,74,65,61}의 네 개의 수가 남게 된다.

입력:

첫째 줄에 A(1<=A<=9999),P(1<=P<=5)가 주어진다.

출력:

첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다.

풀이방법:

 DFS를 사용해서 풀어야 하는 문제이다. check라는 배열을 250000이라고 설정하고(최대 나올 수 있는 값은 9^5+9^5+9^5+9^5 이기 때문이다.) dfs로 하나씩 들어가면서 해당하는 값에 count를 할당한다. 이렇게 계속해서 값을 구하다가 check가 0이 아닌 값을 만난다면 그 값부터는 반복된다는 뜻이므로 그 check의 count에 1을 뺀 값이 정답이 되게 된다.

 이 문제로 예시를 들면 check[57]에 count를 1을 할당. ->check[74]에 2를 할당 -> check[65]에 3을 할당 -> check[61]에 4를 할당 -> check[37]에 5를 할당 -> check[58]에 6을 할당 -> check[89]에 7을 할당 -> check[145]에 8을 할당 -> check[42]에 9를 할당 -> check[20]에 10을 할당 -> check[4]에 11을 할당 -> check[16]에 12를 할당 -> check[37]에는 이미 5가 할당되어 있음. 따라서 57, 74, 65, 61만 남아야 하므로 답은 5-1인 4가 된다.

문제링크:

https://www.acmicpc.net/problem/2331