C++
-
백준(BOJ) 2231번 분해합알고리즘 풀이/백준(Boj) 2019. 8. 14. 14:26
문제 : https://www.acmicpc.net/problem/2231 문제어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오. 나의 풀이: N의 가장 작은 생성자를 구해야 하고 N이 100만 까지이니 1부터 시작하는 완전 탐색으로 충분히 시간 내에 가능하다. i를 1부터 시작해서 i의 수 +..
-
백준(BOJ) 2294번 동전 2알고리즘 풀이/백준(Boj) 2019. 8. 13. 16:27
문제 : https://www.acmicpc.net/problem/2294 문제n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 나의 풀이:반복적 동적 계획법을 통해 해결해보자 . cache[i] 는 i 원을 만들 수 있는 최소 동전의 수로 놓고 동적 계획법을 짜보자 예제 ) 코드 ( C++ ) #include #include using namespace std;int n, k;int coin[101];int cache[10001];const int INF = 987654321;int solve()..
-
백준(BOJ) 1620번 나는야 포켓몬 마스터 이다솜알고리즘 풀이/백준(Boj) 2019. 8. 12. 15:13
문제 : https://www.acmicpc.net/problem/1620 문제 오박사 : 그럼 다솜아 이제 진정한 포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라. 일단 네가 현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라. 나의 시험을 통과하면, 내가 새로 만든 도감을 주도록 하겠네. 나의 풀이: N과 M이 10만 이기때문에 완전탐색으로는 10만 * 10만이 되어서 시간 내에 불가능하다. 이분탐색으로 접근하여야 가능하다. 그런데 숫자가 주어젔을 경우 에는 이분탐색으로 접근하지 않고 바로 인덱스로 접근해도 해결이 가능하다. 따라서 숫자시 인덱스로 바로 접근 , 알파벳일시 이분 탐색으로 접근해주자. ..
-
백준(BOJ) 7569번 토마토알고리즘 풀이/백준(Boj) 2019. 8. 11. 02:04
문제 : https://www.acmicpc.net/problem/7569 문제철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된..
-
백준(BOJ) 1389번 케빈 베이컨의 6단계 법칙알고리즘 풀이/백준(Boj) 2019. 8. 10. 02:27
문제 : https://www.acmicpc.net/problem/1389 문제케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-..
-
백준(BOJ) 2437번 저울알고리즘 풀이/백준(Boj) 2019. 8. 9. 16:23
문제 : https://www.acmicpc.net/problem/2437 문제하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 나의 풀이: 사용 가능한 무게추들을 오름차순 정렬한다. 그 후 정렬된 가장..
-
백준(BOJ) 1405번 미친 로봇알고리즘 풀이/백준(Boj) 2019. 8. 9. 02:01
문제: https://www.acmicpc.net/problem/1405 문제통제 할 수 없는 미친 로봇이 평면위에 있다. 그리고 이 로봇은 N번의 행동을 취할 것이다.각 행동에서 로봇은 4개의 방향 중에 하나를 임의로 선택한다. 그리고 그 방향으로 한 칸 이동한다.로봇이 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다. (로봇이 시작하는 위치가 처음 방문한 곳이다.) 로봇의 이동 경로가 단순할 확률을 구하는 프로그램을 작성하시오. 예를 들어, EENE와 ENW는 단순하지만, ENWS와 WWWWSNE는 단순하지 않다. (E는 동, W는 서, N은 북, S는 남) 나의 풀이: 상하좌우로 최대 14번 갈 수 있으므로 MAX를 넉넉히 30으로 잡자. 방문경로를 나타내는 vis..
-
백준(BOJ) 1427번 소트인사이드알고리즘 풀이/백준(Boj) 2019. 8. 8. 16:17
문제 : https://www.acmicpc.net/problem/1427 문제배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자. 나의 풀이: n의 끝자리수 부터 하나씩 배열에 저장한다. 그 후에 sort 를 통해 정렬해준다. sort는 퀵 소트 기반으로 nlgn을 보장하는 알고리즘으로 짜 여있다. 따라서 시간 이내에 정렬이 가능하다. 풀이 ( C ++ ) #include #include #include using namespace std;// 정렬 기준 정하기bool compare(int a, int b){return a > b;}int main(){ios_base::sync_with_stdio(false);cin.tie(0);int n;cin >> n;vecto..