BOJ
-
백준(BOJ) 1931번 회의실배정알고리즘 풀이/백준(Boj) 2019. 7. 19. 01:19
문제 : https://www.acmicpc.net/problem/1931 문제한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 풀이:회의가 끝나는 시간으로 오름차순으로 정렬한다. 정렬된 배열의 첫 번째 회의는 무조건 선택한다. 그 후 겹치는 회의를지울 필요 없이 정렬된 배열을 순회하면서 첫 번째 회의..
-
백준(BOJ) 1699번 제곱수의 합알고리즘 풀이/백준(Boj) 2019. 7. 18. 13:44
문제: https://www.acmicpc.net/problem/1699 문제어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오. 나의 풀이: 어떤 한 수를 제곱수의 합으로 나타낸다면 그 수의 ..
-
백준(BOJ) 2156번 포도주 시식알고리즘 풀이/백준(Boj) 2019. 7. 16. 15:07
문제 : https://www.acmicpc.net/problem/2156 문제효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다.효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양..
-
백준(BOJ) 10026번 적록색약알고리즘 풀이/백준(Boj) 2019. 7. 16. 00:57
문제 : https://www.acmicpc.net/problem/10026 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오. 나의풀이 : 색약이 아닐 경우 R,G,B 한번씩 DFS를 통하여 답을 구하고 색약일 경우 구역에 G들을 R로 바꾼후 R,B 한번씩 DFS를 통하여 답을 구하여 출력하였다. 코드 ( C ++ ) #include #include #include using namespace std;int N;const int MAX = 101;char sec..
-
백준(BOJ) 1932번 정수 삼각형알고리즘 풀이/백준(Boj) 2019. 7. 15. 23:56
문제 : https://www.acmicpc.net/problem/1932 위 그림은 크기가 5인 정수 삼각형의 한 모습이다.맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다. 나의풀이 : 삼각형을 왼쪽으로 다 붙여서 직각삼각형으로 시작하자.y = 0 , x =0 에서 출발하여 바로 아래 ( y= 1, x =0 ) 과 대각선 ( y =1 , x =1 ) 로 나아 갈..
-
백준(BOJ) 2193번 이친수알고리즘 풀이/백준(Boj) 2019. 7. 15. 01:28
문제 : https://www.acmicpc.net/problem/2193 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.이친수는 0으로 시작하지 않는다.이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오. 나의풀이 : 동적계획법은 항상 완전탐색에서 시작하듯 이친수를 일단 직..
-
백준(BOJ) 1969번 DNA알고리즘 풀이/백준(Boj) 2019. 7. 15. 00:42
문제 : https://www.acmicpc.net/problem/1969 입력첫 줄에 DNA의 수 N과 문자열의 길이 M이 주어진다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 DNA가 주어진다. N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다.출력첫째 줄에 Hamming Distance의 합이 가장 작은 DNA 를 출력하고, 둘째 줄에는 그 Hamming Distance의 합을 출력하시오. 그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다. 나의풀이 : 전체 문자들을 세로로 비교해가면서 가장 높은 숫자들을 선택해준후 벡터에 넣는다. 숫자는 골라졌지만 가장 높은 숫자는 아닌 혹은 사전순으로 우선 순위가 아래인 숫자들의 수를 subsum을 통해..
-
백준(BOJ) 1003번 피보나치 함수알고리즘 풀이/백준(Boj) 2019. 7. 11. 16:09
문제 : https://www.acmicpc.net/problem/1003 입력첫째 줄에 테스트 케이스의 개수 T가 주어진다.각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.출력각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. 나의풀이: f(0)의 0과 1의 수 : 1 0f(1)의 0과 1의 수 : 0 1f(2)의 0과 1의 수 : 1 1f(3)의 0과 1의 수 : 1 2f(4)의 0과 1의 수 : 2 3f(5)의 0과 1의 수 : 3 5 f(n) 은 f(n-2) + f(n-1) 를 세로로 각각 더해주면 나온다는 것을 알 수 있다. 그림에 보듯 f(n)의 0의수는 f(n-1)의 1의 수와 똑같기에 f(n..