CodeDrive

문제:

재현이는 다음과 같은 정수 게임을 하려고 한다. 게임은 다음과 같이 이루어져 있다.

 1. 정수 N과 크기가 K인 배열 A를 정한다.

 2. 1부터 N까지 정수를 모두 종이에 쓴다.

 3. 배열 A의 가장 첫 수를 고르고, 그 수를 배열에서 제거한다. 고른 수를 x라고 했을 때, 종이에 적혀있는 수 중에 x의 배수를 지운다.

 4. 배열이 비어있을 때 까지 3번을 반복한다.

게임이 모두 완료된 이후에, 종이에 적혀있는 수의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 K가 주어진다. (1<=N<=1,000,000,000, 1<=K<=15)

둘째 줄에 배열 A의 내용이 순서대로 주어진다. 배열에 담겨있는 수는 100보다 작거나 같은 자연수이다.

출력:

게임이 모두 완료된 이후에, 종이에 적혀있는 수의 개수를 출력한다.

풀이방법:

포함배제의 원리를 사용해서 풀어야 하는 문제이다. 포함배제의 원리는 유한 집합들의 합집합의 원소를 세는 기법 중의 하나이다. 보통 다음과 같은 식을 가진다.

따라서 count를 통해서 현재 값을 더해야 하는지 빼야 하는지를 결정해준다. 해당하는 값들은 combination으로 만든 조합의 최소공배수 값을 통해서 지워야 하는 갯수를 구할 수 있다.

이렇게 포함배제로 지워지는 수들의 갯수를 구하면 n과 더해줌으로써 남은 개수를 구한다.

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

https://ko.wikipedia.org/wiki/%ED%8F%AC%ED%95%A8%EB%B0%B0%EC%A0%9C%EC%9D%98_%EC%9B%90%EB%A6%AC

문제:

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계까 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다."를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력:

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

풀이방법:

bfs를 사용해서 이 문제를 풀었다. 이 문제에서는 신뢰 관계가 양방향으로 존재한다는 가정이 없기 때문에 신뢰 관계를 정리 할 때, 단방향으로만 해야 한다. 일반적인 리스트를 사용해도 상관이 없지만 python의 시간 초과를 해결하기 위해 deque를 사용하고자 하였다. 하지만 그래도 python으로는 시간초과가 발생하였고,(한 명도 python으로 통과한 사람이 아직 없다.)그래서 결국 pypy3으로 통과했다.

 그 외의 특이사항으로는 방문했는지 확인하는 배열인 conti가 존재한다는 것이다. 아직 방문하지 않는 컴퓨터일 때에만 값을 갱신하며 count가 증가하도록 했다.

문제링크:

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

문제:

2019/10/29 - [Algorithm/Python] - [BOJ]7576. 토마토

 위 문제에서 더 발전한 문제로 이제 한 층이 아닌 여러 층에 대해서 토마토가 익는 것이 전이된다.

입력:

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2<=M<=100,2<=N<=100,1<=H<=100이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

출력: 

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산하여 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

풀이방법:

 이전문제에선 2차원 배열로 받았지만, 이번에는 3차원 배열로 작성한다. 또한 위, 아래로도 이동해야 하기 때문에 dx,dy,dn 세 가지 변수를 사용했다. 이외에는 이전문제와 동일한 풀이로 풀었다.

문제링크:

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

문제:

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익에 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 탄에는 토마토가 들어있지 않을 수도 있다.

입력:

첫 줄에는 상자의 크기를 나타내는 두 정수 M, N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단 2<=M,N<=1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 잊지 않는 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

출력:

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지 못하는 상황이면 -1을 출력해야 한다.

풀이방법:

BFS를 사용해서 풀어야 하는 문제이다. 우선 1이 있는 위치를 파악을 하고 이를 queue에 넣어 준다. 그 뒤에 1을 하나씩 빼면서 옆에 있는 토마토를 익게 만들 수 있는지 계산을 한다. 이 때 change라는 bool 변수를 만들어서 하나의 토마토라도 queue 진행 중에 익게 된다면 True로 바뀌어서 다음 진행을 계속해서 하도록 한다. 만약 익게 되는 토마토가 없어서 False로 남아 있다면 다 익어서 종료가 된 것인지, 혹은 모두 익지 못하는 상황인지 전체를 한 번 탐색하여 파악한다.

처음부터 모두가 익어 있으면 0을 출력해야 하지만 첫 count는 항상 1부터 시작하기 때문에 count-1을 한 값을 출력하면 답을 얻을 수 있다.

문제링크:

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

문제:

Day of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.

끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의  가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어진다. 가격은 0보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력:

첫째 줄에 기타줄을 적어도 N개 사기 위해 필요한 돈의 최솟값을 출력한다.

풀이방법:

여러 개의 기타줄에서 패키지 가격이 가장 작은 값과, 낱개 가격이 가장 작은 값만 필요하다. 이 두 개의 가격을 비교했을 때, 만약 낱개로 6개를 사는 것이 패키지 가격보다 싸다면 모든 기타줄을 낱개로 사는 것이 이득이다.

만약 그렇지 않다면 사야하는 기타줄을 6으로 나눴을 때 그 몫만큼은 패키지로 사는 것이 이득이다. 그 뒤로는 남은 나머지를 낱개로 샀을 때와 패키지로 샀을 때(적어도 N개를 구매하면 되므로 초과해서 사도 괜찮다.) 어떤 것이 이득인지 알아보고 그에 맞게 구매를 해야 한다. (ex 패키지 7 낱개 2면 패키지가 더 이득)  

문제링크:

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

문제:

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 상근이의 동기의 수 n(2<=n<=500)이 주어진다. 둘째 줄에는 리스트의 길이 m(1<=m<=10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai,bi가 주어진다. (1<=ai<bi<=n) ai와 bi가 친구라는 뜻이며, bi 와 ai도 친구관계이다.

출력:

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

풀이방법:

우선 입력으로 받은 값들을 그래프 형식으로 정리를 하는 작업을 거친다. 이후 BFS 방식을 사용해서 level이 2까지 가는 친구들(친구의 친구)을 찾는다. 항상 시작은 1이므로 queue에 1을 넣고 BFS 탐색을 두번 한다. 그렇게 탐색을 마치고 1을 제거한 뒤에 배열의 길이를 출력하도록 한다.

문제링크:

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

문제:

상근이는 농구의 세계에서 점차 영향력을 넓혀가고 있다. 처음에 그는 농구 경기를 좋아하는 사람이었다. 농구에 대한 열정은 그를 막을 수 없었고, 결국 상근이는 농구장을 청소하는 일을 시작했다. 상근이도 농구장을 청소하면서 감독이 되기 위해 가져야할 능력을 공부해나갔다. 서당개 3년이면 풍월을 읊듯이 상근이는 점점 감독으로 한 걸음 다가가고 있었다. 어느 날 그에게 지방의 한 프로농구팀을 감독할 기회가 생기게 되었다. 그는 엄청난 지도력을 보여주며 프로 리그에서 우승을 했고, 이제 국가대표팀의 감독이 되었다.

내일은 일본과 국가대표 친선 경기가 있는 날이다. 상근이는 내일 경기에 나설 선발 명단을 작성해야 한다.

국가대표팀의 감독이 된 이후에 상근이는 매우 게을러졌다. 그는 선수의 이름을 기억하지 못하고, 각 선수의 능력도 알지 못한다. 따라서, 누가 선발인지 기억하기 쉽게 하기 위해 성의 첫 글자가 같은 선수 5명을 선발하려고 한다. 만약, 성의 첫 글자가 같은 선수가 5명보다 적다면, 상근이는 내일 있을 친성 경기를 기권하려고 한다.

상근이는 내일 경기를 위해 뽑을 수 있는 성의 첫 글자를 모두 구해보려고 한다.

입력:

첫째 줄에 선수의 수 N(1<=N<=150)이 주어진다. 다음 N개 줄에는 각 선수의 성이 주어진다. (성은 알파벳 소문자로만 이루어져 있고, 최대 30글자이다)

출력:

상근이가 선수 다섯 명을 선발할 수 없는 경우에는 "PREDAJA" (따옴표 없이)를 출력한다. PREDAJA는 크로아티아어로 항복을 의미한다. 선발할 수 있는 경우에는 가능한 성의 첫 글자를 사전순으로 공백없이 모두 출력한다.

풀이방법:

딕셔너리 자료형을 사용해서 해시 방법으로 풀었다. 맨 앞글자를 키로 하고 그에 따른 value는 나타낸 횟수로 지정했다. 이렇게 모든 이름을 다 한번씩 탐색해 딕셔너리로 정리를 마친다. 이를 items으로 가져와서 정렬한 뒤에 5이상인 값만 answer에 붙이도록한다. 만약 5이상인 값이 없었다면 answer는 빈 문자열일것이다.

문제링크:

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

문제:

어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱 ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱 ㄴㄴ수가 몇 개 있는지 출력한다.

입력:

첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000.000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 [min,max]구간에 제곱ㄴㄴ 수가 몇 개인지 출력한다.

풀이방법:

어떤 수 X가 한 제곱수로 나누어지는지 확인하는 것 보다 제곱수가 나누어 떨어지게 만들 수 있는 수들을 지워나가는 것이 시간복잡도를 줄일 수 있다.(에라토스테네스의 체와 비슷)

문제링크:

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

문제:

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

이 알고리즘은 다음과 같다.

 1. 2부터 N까지 모든 정수를 적는다.

 2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.

 3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.

 4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

입력:

첫째 줄에 N과 K가 주어진다. (1<=K<,max(2,K) < N <=1000)

출력:

첫째 줄에 K번째 지워진 수를 출력한다.

풀이방법:

우선 N까지 수가 있는 배열을 만들고 이를 에라토스테네스의 체 규칙에 따라서 하나씩 지워나간다. 이 때마다 하나씩 count를 늘려주면서 K번째가 되면 현재 지운 값을 출력하도록 한다.

문제링크:

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

문제:

슈퍼 마리오 앞에 10개의 버섯이 일렬로 놓여져 있다. 이 버섯을 먹으면 점수를 받는다.

슈퍼 마리오는 버섯을 처음부터 나온 순서대로 집으려고 한다. 하지만, 모든 버섯을 집을 필요는 없고 중간에 중단할 수 있다.

중간에 버섯을 먹는 것을 중단했다면, 그 이후에 나온 버섯은 모두 먹을 수 없다. 따라서 첫 버섯을 먹지 않았다면, 그 이후 버섯도 모두 먹을 수 없다.

마리오는 받은 점수의 합을 최대한 100에 가깝게 만들려고 한다.

버섯의 점수가 주어졌을 때, 마리오가 받는 점수를 출력하는 프로그램을 작성하시오.

입력:

총 10개의 줄에 각각의 버섯의 점수가 주어진다. 이 값은 100보다 작거나 같은 양의 정수이다. 버섯이 나온 순서대로 점수가 주어진다.

출력:

첫째 줄에 마리오가 받는 점수를 출력한다. 만약 100에 가까운 수가 2개라면 (예: 98, 102) 마리오는 큰 값을 선택한다.

풀이방법:

반복문을 사용해서 0개 버섯을 먹은 경우부터 10개의 버섯을 먹은 모든 경우를 모두 한 배열에 담아 넣는다. 그 다음에는 python의 sort의 key 기능을 사용해서 100과 가까운 수가 제일 앞에 오도록 정렬을 했다. (abs(x-100)을 이용해서) 그 다음에는 98과 102와 같이 간격이 같은 경우가 있을 수 있으므로 이 경우에는 1번째 인덱스를, 아닌 경우에는 0번째 인덱스를 출력하도록 했다.

문제링크:

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