trudy

1912번: 연속합 (acmicpc.net) 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net [백준/BOJ] 1912번 연속합 (C/C++) (tistory.com) [백준/BOJ] 1912번 연속합 (C/C++) 백준 온라인 저지(BOJ) 1912번 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 rightbellboy.tistory.com..

2193번: 이친수 (acmicpc.net) 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 규칙을 알아봅시당 1로 시작하고 11이 나오면 안되므로 아이디어 1) n>1 일 때는 10_ 으로 시작해야한다 아이디어 2) 조합을 생각했을 때, 10 다음부터는 0,1로 채워지되 1만 연속하게 안나오게 만들면 됨 ex) T(5) = 2^4 - 6 = 10 T(6) = 2^5 - 10 = 22 n=1일 때, 1가지 (1) n=2일 때, 1가지 (10) n=3일 때, 2가지 (10_: 100, 101) n=4..

1463번: 1로 만들기 (acmicpc.net) 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 규칙을 찾아봅시다 X=2일 때, 1 (2/2=1) X=3일 때, 1 (3/3=1) X=4일 때, 2 (4/2=2 2/2=1) X=5일 때, 3 (5-1=4, 4/2=2 2/2=1) X=6일 때, 2 (6/3=2, 2/2=1) X=7일 때, 3 (7-1=6, 6/3=2, 2/2=1) 1. 3의 배수일 때 => 3으로 나눔 2. 3의 배수가 아니고 2의 배수일 때 => 2로 나눔 3. 2의 배수, 3의 배수도 아닐 때 => 1을 뺌 T(4) = 1+ T(2) T(5) = 1+T(4) T(6) = 1+T(2) T(7) = 1+T(6..

9095번: 1, 2, 3 더하기 (acmicpc.net) 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net DP니까 규칙을 찾아봅시당 n=1 일 때, 1가지 1 n=2 일 때, 2가지 1 + 1 = 2 n=3 일 때, 4가지 1+1+1 = 1+2 = 2+1 = 3 n=4 일 때, 7가지 1+1+1+1 = 1+1+2 = 1+2+1 = 2+1+1 = 2+2 = 1+3 = 3+1 n=5 일 때, 13가지 1+1+1+1+1 = 1+1+1+2 = 1+1+2+1 = 1+2+1+1 = 2+1+1+1 = 1+2+2 = 2+1+2 = 2+2+1 = 1+1+3 = 1+3+1 = 3+1+1 = 2+3 = 3+2 점화식이 T(n..

11727번: 2×n 타일링 2 (acmicpc.net) 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 규칙을 알아보자! n=1 일 때, 1가지 n=2 일 때, 3가지 n=3 일 때, 5가지 (모두 세로 1가지 + 1개만 세로 2가지, 2*2 한개가 포함된 거 2가지) n=4 일 때, 11가지(모두 세로 1가지, 모두 가로 1가지+ 2개만 가로 3가지+ 2*2 한개가 포함된 거 5가지+ 2*2 두개가 포함된 거 1가지) n=5 일 때, 21가지 1. 모두 세로: 1가지 2. 세로 1개, 가로 4개: 3개 3. 세로 3개, 가로 2개: 4개..

11726번: 2×n 타일링 (acmicpc.net) 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 규칙성을 알아보기 위해 일일이 구해보면.. n=1 일 때, 1가지 n=2 일 때, 2가지 n=3 일 때, 1+2 = 3가지 (모두 세로로 서 있는 거 1가지 + 한개만 세로로 있고 2개가 누워있는 거 2가지) n=4 일 때, 2+3 = 5가지 (모두 세로로 서 있는 거 1가지 + 모두 누워있는 거 1가지, 2쌍만 누워있는거 3가지) n=5 일 때, 8가지 n=6일때, 13가지 n=7일때, 21가지 n=8일때 34가지 n=9일때, 5..

9461번: 파도반 수열 (acmicpc.net) 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 규칙성을 찾는 게 중요한 다이나믹 프로그래밍 유형,, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 점화식을 세워보면 P(1) = 1 P(2) = 1 P(3) = 1 n>3일 때, P(n) = P(n-3) + P(n-2) 또,, 가장 쉽게 생각할 수 있는 재귀 방법으로 풀었는 데 시간 초과가 떴다 #include using namespace std; int pado(int n) { if(n==1 | n==2 | ..

1003번: 피보나치 함수 (acmicpc.net) 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제가 풀리는 가장 간단한 방법으로 풀었더니 시간초과가 떴다 #include using namespace std; int z, o; int fibonacci(int n) { if (n == 0) { z++; return 0; } else if (n == 1) { o++; return 1; } else { return fibonacci(n-1) + fibonacci(n-2); } } int main() { int t, n; cin >> t; for(int i=0; i> n; fibonacci(n); cout

10989번: 수 정렬하기 3 (acmicpc.net) 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 정답률이 낮은 데, 기본적인 정렬 문제고 주어진 범위가 넓길래 시간 초과나 메모리 문제로 다르게 풀어야겠거니 했다 [백준(BOJ)] 10989번 : 수 정렬하기 3 - C++[CPP] (tistory.com) [백준(BOJ)] 10989번 : 수 정렬하기 3 - C++[CPP] www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진..

18870번: 좌표 압축 (acmicpc.net) 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 문제 이해가 너무 어려웠던 문제 문제 설명이 너무 불친절해요 그래서 구글링해서 해설을 좀 읽어보니까 이해한게 좌표 압축이라는 것은 좌표를 중복되지 않는 집합에 넣어뒀을 때, 자신보다 작은 원소의 개수로 자신의 수를 바꾸는 것 그럼 그렇게 하기 위해서는 배열을 받고, 오름차순으로 정렬을 해준 뒤, 중복되는 원소를 제거해주고, 자신보다 왼쪽에 있는 원소의 개수를 세어..