백번 열번 백번 열번

C++

• 백준(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 ..

  Read More
• 백준(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; //..

  Read More
• 백준(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 == ..

  Read More
• 비대칭 타일링

  알고리즘 풀이/알고리즘 해결전략 연습 2019. 7. 7. 02:48

  문제 : https://algospot.com/judge/problem/read/ASYMTILING 입력입력의 첫 줄에는 테스트 케이스의 수 C (1

  Read More
• 백준(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;..

  Read More
• 삼각형 위의 최대 경로 수 세기

  알고리즘 풀이/알고리즘 해결전략 연습 2019. 7. 7. 00:23

  문제 : https://algospot.com/judge/problem/read/TRIPATHCNT 코드 ( C ++ ) 종만북 참조 #include #include using namespace std;const int MAX = 100+1;int N;int triangle[MAX][MAX];int path[MAX][MAX];int cache[MAX][MAX]; int count(int y, int x){if (y == N - 1) return 1;int& ret = cache[y][x];if (ret != -1)return ret;ret = 0;if (path[y + 1][x + 1] >= path[y + 1][x]) ret += count(y + 1, x + 1);if (path[y + 1][x + ..

  Read More
• 백준(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..

  Read More
• 백준(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]이 ..

  Read More