펭로그

문제링크 : https://noj.am/9095 어떤 숫자 N을 1, 2, 3 더하기로 나타내는 방법은 다음과 같다.[1] - 1개1 [2] - 2개1+1 → [1]+12 [3] - 4개1+2 → [1]+21+1+1, 2+1 → [2]+13 [4] - 7개 (1+2+4)1+3 : [1]+3 → [1] + 31+1+2, 2+2 → [2] + 21+2+1, 1+1+1+1, 2+1+1, 3+1 → [3] + 1 [5] - 13개 (2+4+7)1+1+3, 2+3 → [2] + 31+2+2, 1+1+1+2, 2+1, 3+2 → [3] + 21+3+1, 1+1+2+1, 2+2+1, 1+2+1+1, 1+1+1+1+1, 2+1+1+1, 3+1+1 → [4] + 1 위와 같이 시뮬레이션을 해보면 DP[N] = DP[N-..

문제링크 : https://noj.am/2583 단순 DFS/BFS 문제이다.계산하기 편하게 (1,1)~(N,M)의 영역을 사용한다.초기에 테두리를 방문한 것으로 체크하고 내부를 미방문한 상태로 초기화 시키면 ▣ Y >> X >> K; // true : 방문, false : 미방문 // 테두리를 방문한 것으로 만들고 내부는 미방문 상태로 초기화 arr = vector(X + 2, vector(Y + 2, true)); for (int i = 1; i > y1 >> x2 >> y2; for (int x = x1 + 1; x

문제링크 : http://codeforces.com/contest/1059 C. Sequence Transformation 각 숫자들을 인수분해 하면 소수들의 곱으로 이루어진다.입력 사이즈가 100만이기 때문에 100만의 제곱근 만큼인 1000까지의 소수를 구하고 그 소수들 중에서 가장 많은 배수들을 가지고 있는 소수를 추려내고 나머지 모든 수를 1로 출력, 그 소수의 제곱수가 아닌 숫자를 그 소수로 출력, 소수의 제곱수를 출력 하는 식으로 문제를 접근했는데.. 답은 맞게 나오겠지만 메모리 공간이 분명 초과되는듯 하다. 기존엔 문제를 이렇게 풀었으나 출력해서 규칙을 보니.. 2의 배수만 신경쓰면 되는 것을 발견했다.3을 제외하고 전부 2로 출력되었으니 말이다.. 12345678910111213141516..

문제링크 : http://codeforces.com/contest/1059 A. Cashier 단순 구현문제로 중간에 비는 시간에 담배탐을 할 수 있는 시간이 있는지 체크하여 누적하고 업무가 끝나고 남은 시간도 담배탐을 할 수 있는 만큼 더해준다. 12345678910111213141516171819202122232425262728293031323334353637// Codeforces Round #514 (Div. 2)// A. Cahier#include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); freopen("../input.txt", "r", std..

문제링크 : https://noj.am/13458 단순 구현 문제인데 정답률이 25%대로 낮은 문제이다.그 이유는 출력 자료형을 다들 고려하지 않아서 그런 것 같다.최대로 나올 수 있는 값이 1,000,000 * 1,000,000이기 때문에 long long 타입을 사용해야한다. 1234567891011121314151617181920212223242526272829303132// BOJ 13458 시험 감독#include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);// freopen("../input.txt", "r", stdin); int num, main, su..

문제링크 : https://boj.am/1991 문제에서 입력은 A~Z로만 한정되어 있다. 이러한 특성 덕분에 간단한 형태로 트리를 구현할 수 있다.char 형태의 A(65) ~ Z(90)에서 A(65)씩 빼주면 A(0) ~ Z(25)로 표현할 수 있기 때문이다.따라서, 인덱스 번호 자체가 노드에 들어있는 문자를 의미하는 것이기 때문에 2개의 배열 만으로도 트리의 구현이 가능하다. 현재 노드를 V, 좌측 자식 노드를 L, 우측 자식노드를 R이라고 한다면전위순회는 V-L-R 순서로중위순회는 L-V-R 순서로후위순회는 L-R-V 순서로 순회하게 된다. 스택을 이용하여 구현을 하려고 시도해봤으나 너무 복잡하여 재귀로 구현했다. 1234567891011121314151617181920212223242526272..

문제링크 : https://noj.am/8916 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071// BOJ 8916 이진 검색 트리#include using namespace std; long long comb(int n, int r) { // nCr r = n - r > r ? r : n - r; long long result = 1; for (int i = 0; i tc; while (tc--) { int num, input; vector tree(1); cin >> num; while(num--) { int i..

문제링크 : https://noj.am/11403 전형적인 BFS / DFS 문제그냥 풀면 된다. 자기 자신노드로 돌아오는 경우가 있기 때문에 맨 처음은 방문체크를 하지 않았다.인접리스트는 graph[0] = {1, 3, 5, 6, 7} 이런 형태로 저장된다. 현재 노드에서 해당 노드로 갈 수 있으면 저장된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253// BOJ 11403 경로 찾기#include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cou..

문제링크 : https://noj.am/1759 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192// BOJ 1759 암호 만들기#include #include #include using namespace std; vector arr; // 전체 문자vector mo; // 모음vector answer; // 정답 문자vector expt; // 검색 제외vector result; // 출력int size, inp; // 문자열 길이, 입력 크..

문제링크 : https://boj.kr/11726 시뮬레이션을 해보면 아래 그림과 같이 규칙을 찾을 수 있다.하나의 타일을 1*2로 고정 시키면 N-1의 모든 케이스를 적용할 수 있고두개의 타일을 2*1 두개로 고정 시키면 N-2의 모든 케이스를 적용할 수 있다. 하지만, 여기서 신기한 점은 1, 2, 3, 5.... 피노나치 수열과 동일한 문제임을 알 수 있다. 12345678910111213141516171819202122232425// BOJ 11726 2xn 타일링#include using namespace std; int dp[1001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen..