본문 바로가기

전체 글

Baekjoon 14890 경사로 2019. 4. 1. Link https://www.acmicpc.net/problem/14890 소스결과 2088 KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 시뮬레이션 설명 N x N 지도가 주어졌을 때 l길이의 경사로를 놓아 지나갈 수 있는 경로의 갯수를 출력해준다. 경사로를 놓기 위해서는 높이의 차이가 1이어야한다. 또한 경사로는 겹쳐서 놓을 수가 없다. 범위를 벗어나서는 안된다. 경사로의 개수는 무제한이다. 위 조건을 만족 하기 위해서 경사로를 놓은 위치를 기억해야한다. 각 줄에 대해서 독립 시행이기때문에 과거의 결과를 저장하면 안됬었다. 세로와 가로가 같은 방식의 알고리즘이지만 한개의 함수로 묶어서 구현하면 생각보다 구현이 복잡해 나눠서 구현했다. BFS/DFS가 없는 순수한 구현 문제이기때문에 ..
Baekjoon 1964 오각형, 오각형, 오각형... 2019. 4. 1. Link https://www.acmicpc.net/problem/1964 소스결과 1988 KB / 36 ms 출처 Baekjoon 언어 C++ 17 분류 수학 설명 그림과 같은 오각형의 점의 개수를 45678로 나눈 나머지를 출력한다. 그림 속 값이 늘어나는 일정한 규칙을 찾자. 과거 도형과 겹치는 부분을 제외하면 길이가 1 늘어난 변이 3개 존재하고 겹치는 점이 2개 존재한다. % 연산자의 특성을 고려해 결과값을 계산해 나가면 된다. 알고리즘 1. n을 입력 받는다. 2. 현재까지의 오각형 점의 수를 45678로 나눈 값 + 이번에 새로 추가된 점의 수 % 45678을 현재 5각형의 수로 정한다. 초기값은 5 3. 출력한다. 소스코드 #include using namespace std; const ..
Baekjoon 1904 01타일 2019. 4. 1. Link https://www.acmicpc.net/problem/1904 소스결과 5892 KB / 8 ms 출처 Baekjoon 언어 C++ 17 분류 다이나믹 프로그래밍 설명 00 또는 1 로만 구성된 길이가 N인 2진 수열의 개수를 구하자 N이 5일 때 까지의 결과값들은 1, 2, 3, 5, 8 이다. 피보나치 수열이다. 알고리즘 1. n을 입력 받는다. 2. 1 ~ 100만까지의 피보나치 수열을 구한다. 각각의 값은 15746으로 나눈 나머지로 구한다. 3. n번째에 있는 값을 출력해준다. 소스코드 #include using namespace std; const int MAX = 1000000; const int DIV = 15746; int dp[MAX] = { 1, 2, }; int main..
Baekjoon 1789 수들의 합 2019. 4. 1. Link https://www.acmicpc.net/problem/1789 소스결과 1984 KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 수학 설명 서로 다른 N개의 자연수의 합으로 이루어진 n 이 주어질 때 N의 최대 값을 구하여라. 1 ~ X 까지의 합이 처음으로 n보다 커지는 X를 구하면 된다. 알고리즘 1. N을 입력 받는다. 2. 1부터 1 씩 증가하며 ( i + 1 ) * ( i + 2 ) / 2가 n보다 커지기 전까지 반복한다. 3. 2를 처음으로 만족시키지 못하는 i를 출력한다. 소스코드 #include using namespace std; int main() { long long n; cin >> n; long long res = 1; for (; (res + 1) * ..
Baekjoon 1977 완전제곱수 2019. 4. 1. Link https://www.acmicpc.net/problem/1977 소스결과 1988KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 수학 설명 M ~ N 사이에 존재하는 완전 제곱수를 찾아 수의 합과 최소값을 출력하자. 완전제곱수의 개념만 알면 쉽다. 최적화도 가능하지만 최대 범위가 100 이기 때문에 1부터 진행하자. 1부터 제곱 했을때 M ~ N 사이에 있다면 합에 더하고 최소값을 갱신한다. 알고리즘 1. M, N을 입력 받는다. 2. 1부터 100까지 반복한다. 2 - 1. 현재 수를 제곱 했을 때 M ~ N 범위안에 포함되는지 확인한다. 2 - 2. 포함이 된다면 최소값인지 판별한 후 갱신한다. 2 - 3. 포함 된다면 합에 더한다. 3. 2를 통해 구해진 값이 없다면 -1을..
Baekjoon 1463 1로 만들기 2019. 4. 1. Link https://www.acmicpc.net/problem/1463 소스결과 2964KB / 0ms 출처 Baekjoon 언어 C++17 분류 다이나믹프로그래밍, BFS 설명 주어진 n을 특정 연산을 통해 1로 만드는 횟수의 최소값을 구한다. 문제 분류가 DP지만 BFS로 해결된다. 결과값이 최대 10만이기때문에 가능한것 같다. 3으로 나눈경우, 2로 나눈경우, 1 뺀 경우 3개로 나누어서 BFS를 진행한다. 알고리즘 1. n을 입력 받는다. 2. n을 Queue에 넣은 후 방문 처리한다. 3. Queue에서 원소를 꺼낸후 3으로 나눈경우, 2로 나눈경우, 1로 나눈경우를 연산하고 방문하지 않은 값이면 nextQueue에 넣는다. 4. Queue의 원소가 없다면 nextQueue의 원소를 전부 Q..
Baekjoon 1212 8진수 2진수 2019. 3. 31. Link https://www.acmicpc.net/problem/1212 소스결과 2312 KB / 32 ms 출처 Baekjoon 언어 C++ 17 분류 진법, 수학 설명 주어진 8진수를 2진수로 출력하자. 문제는 크게 어렵지 않다. 8진수와 2진수의 관계만 안다면. 2진수를 3자리씩 묶어 10진수로 변환하면 8진수가 된다. 위 문제는 반대로 만들면 된다. 알고리즘 1. 8진수를 입력 받는다. 2. 첫자리인경우 1,2,3 에 한정해 직접 출력한다. 3. 나머지 자리는 8진수를 2진수로 변환한 결과를 출력한다. 소스코드 #include #include using namespace std; const int MAX = 333334; char input[MAX+1]; void oct2Dex(char o) ..
Baekjoon 1037 약수 2019. 3. 31. Link https://www.acmicpc.net/problem/1037 소스결과 1988 KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 수학 설명 N의 n개 진짜 약수가 주어질 때 N을 구하는 프로그램을 만들자 N의 약수중 1과 N이 아닌 약수를 진짜 약수라고 한다. n이 홀수 일 떄와 짝수일 때가 있는데 홀수일 경우는 N이 제곱수이다. N을 구하기 위해서는 최대 값과 최소 값만 알면 상관이 없지만, 이번 문제에서는 정렬을 이용해 최대/최소 값을 구하거나 중앙값을 구하는 방법을 사용했다. 알고리즘 1. n개의 수를 입력 받는다. 2. n개의 수를 오름차순으로 정렬한다. 3. n이 홀수인 경우 중앙값을 제곱해 출력하고, 짝수인 경우 최대값과 최소값을 곱해 출력한다. 소스결과 #inclu..

티스토리툴바