BOJ
-
백준(BOJ) 1568번 새알고리즘 풀이/백준(Boj) 2019. 7. 10. 08:02
문제: https://www.acmicpc.net/problem/1568 입력첫째 줄에 새의 수 N이 주어진다. 이 값은 10^9보다 작거나 같다.출력첫째 줄에 정답을 출력한다. 코드 ( C++ ) #include using namespace std;int N; int main(){cin >> N;int sing = 1;int cnt = 0;while (N != 0) {if (N < sing) // 남아있는 수 보다 sing이 더 커지면 sing을 다시 1로 만든다.sing = 1;N -= sing;sing++;cnt++;}cout
-
백준(BOJ) 9095번 1,2,3 더하기알고리즘 풀이/백준(Boj) 2019. 7. 9. 07:00
문제 : https://www.acmicpc.net/problem/9095 입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.출력각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 나의풀이 : n의 개수가 적기 때문에 완전탐색으로도 가능하나 동적 계획법 연습을 위해 동적계획법으로 풀어 보았다.4를 시작으로 -1 을 빼는 경우 -2를 빼는 경우 -3을 빼는 경우로 나뉘어서 재귀적 함수를 호출한다. 0이 만들어지면 경우의 수 1 반환, 0보다 작다면 0을 반환한다. 중복되어서 계산되는 경우는 메모이제이션을 통해 중복 방지한다. 코드 ( C ++ ) #include #include ..
-
백준(BOJ) 1463번 1로 만들기알고리즘 풀이/백준(Boj) 2019. 7. 8. 03:54
문제:https://www.acmicpc.net/problem/1463입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.출력첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 나의풀이 : 동적 계획법을 통해 풀었다. 런타임 에러가 나온다면 MAX에 0이 5개나 7개는 아닌지 봐보자. 코드 ( C ++ ) #include #include #include #include using namespace std;const int MAX = 10000000;int cache[MAX + 1];const int INF = 987654321;int solve(int x){int& ret = cache[x];if (ret != -1)return ret;if (x == 1) return 0; //..
-
백준(BOJ) 1158번 조세푸스 문제알고리즘 풀이/백준(Boj) 2019. 7. 8. 02:47
문제: https://www.acmicpc.net/problem/1158 나의풀이 : 중간과정에서의 삽입과 삭제가 쉬운 연결리스트를 이용하였다. 복잡도는 O(N * K) 입력첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)출력예제와 같이 조세퍼스 순열을 출력한다. 코드 ( C ++ ) #include #include #include using namespace std;int N, K;int main(){cin >> N >> K;list people;vector result;for (int i = 1; i 0) {for (int i = 0; i < K - 1; ++i) { // 자기포함 K번만큼 돌면서 죽일 kill 포인터를 지정해준다.if (kill == ..
-
백준(BOJ) 1965번 상자넣기알고리즘 풀이/백준(Boj) 2019. 7. 7. 01:42
문제 : https://www.acmicpc.net/problem/1965 입력파일의 첫 번째 줄은 상자의 개수 n (1 ≤ n ≤ 1000)을 나타낸다. 두 번째 줄에는 각 상자의 크기가 순서대로 주어진다. 상자의 크기는 1,000을 넘지 않는 자연수이다.출력첫째 줄에 한 줄에 넣을 수 있는 최대의 상자 개수를 출력한다. 나의풀이: LIS와 동일 코드 ( C ++ ) #include #include #include const int MAX = 1000;int line[MAX];int cache[MAX];int N;using namespace std;int findLongLength(int begin){int& ret = cache[begin];if (ret != -1)return ret;ret = 1;..
-
백준(BOJ) 11727번 2xn 타일링 2알고리즘 풀이/백준(Boj) 2019. 7. 6. 03:07
문제 : https://www.acmicpc.net/problem/11727 입력첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)출력첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 나의 풀이: 2xn 타일링 문제 ( https://100100e.tistory.com/24 ) 와 거의 동일했다. 다른 점은 2x2 타일이 추가 된 것인데 마찬가지로 타일을 어떻게 덮었는지는 상관이 없다. 따라서 n-2를 채우는 방법이 2x2 타일을 쓰는 것과 2*1타일 두개를 가로로 배치한 두가지 방법이 될 것 . 따라서 tiling(n-2) 에 2배를 곱해주면 된다. 코드 ( C + + ) #include #include using namespace std;int N;co..
-
백준(BOJ) 11726번 2xn 타일링알고리즘 풀이/백준(Boj) 2019. 7. 6. 02:45
문제 : https://www.acmicpc.net/problem/11726 입력첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)출력첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 나의풀이 : 세로줄 왼쪽부터 채워나갈수 있는 경우의 수를 생각해보자. 세로로 한개, 가로로 두개 두 경우 이외에는 없기 때문에재귀적으로 구현해주고 n이 1000까지 있기에 완전 탐색으로는 시간 내에 불가능하니 메모이제이션을 적용해서 중복되는 탐색을 방지하자. 코드 ( C ++ ) #include #include using namespace std;int N;const int MAX = 1000;int cache[MAX+1]; // n이 1000일 경우 cache[1000]이 ..
-
백준(BOJ) 1302번 베스트셀러알고리즘 풀이/백준(Boj) 2019. 7. 6. 00:44
#include #include #include #include using namespace std; 문제: https://www.acmicpc.net/problem/1302 입력첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.출력첫째 줄에 가장 많이 팔린 책의 제목을 출력한다. 만약 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞서는 제목을 출력한다. 나의풀이 : pair vector에 책이름과 판매수를 적고 판매수를 기준으로 오름차순 정렬한다. 정렬된 list에서 제일 가장 많이 팔린 중복된 책들만 모..