The Way

백준 온라인 저지(BOJ) 11722번 문제https://www.acmicpc.net/problem/11722 1. 문제 요약수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열의 길이를 구하기. 2. 알고리즘다이나믹 프로그래밍을 사용하여 $O(n^2)$의 시간에 구하는 방법은 생각해보았다. 감소하는 부분 수열이 예를 들어서 {30, 20, 10}일 때, 이는 30 + {20, 10}이라서 길이가 2 + 1이 된 것이라 생각하자.맨 뒤는 길이 1로 저장하고,그 이후는 그 성분을 포함시켰을 때 감소하는 수열이 되는 값들의 길이를 훑고, 그 최댓값에 1을 더한 뒤 저장하면 되겠다.말로 설명하기 약간 어려워서 보충 {10, 30, 10, 20, 20, 10} 1 2 1 (20보다 작은 값 10) 2 2 1 (..

백준 온라인 저지(BOJ) 11399번 문제https://www.acmicpc.net/problem/11399 1. 문제 요약ATM 1대와 그를 이용하려는 N명의 사람이 있다.사람들 각각의 사용시간이 주어질 때, ATM을 이용하는 순서에 따라 소요시간의 합이 달라지게 된다.소요시간의 합의 최솟값을 구하여라. 2. 알고리즘만약 3명이라고 치자.처음 사용하는 사람은 a분, 두번째는 b분, 세번째는 c분 소요된다고 했을 때총 소요시간은 $(a) + (a+b) + (a+b+c) = 3a + 2b + c$이다.앞의 상수 3, 2, 1...은 고정이므로 곱해지는 숫자인 a, b, c가 내림차순이어야 최소가 된다. 짜기 귀찮아서 걍 algorithm에 있는 sorting 씀 3. 코드 #include #include..

백준 온라인 저지(BOJ) 1009번 문제https://www.acmicpc.net/problem/1009 1. 문제 요약1번~10번의 이름을 가진 컴퓨터로 차례대로 분산 처리를 할 때, 마지막 데이터가 처리되는 컴퓨터의 번호는? 2. 알고리즘말은 복잡하지만, $a^b$의 일의 자리 수를 출력하는 문제이다.시간을 단축시키는 방법은 여기를 참고하자. 0일 경우 10으로 출력해야 한다. 3. 코드 #include int pow(int base, int index, int mod = 10) { int r = 1; while (index != 0) { if (index & 1 != 0) r = (r * base) % mod; base = (base * base) % mod; index >>= 1; } retur..

백준 온라인 저지(BOJ) 2444번 문제https://www.acmicpc.net/problem/2444 1. 문제 요약예제와 같이 별을 찍자. 이 때 입력은 5이다. * *** ***** ******* ********* ******* ***** *** * 2. 알고리즘생략 3. 코드 #include using namespace std; int main() { int N; scanf("%d", &N); for (int i = 0; i < N; i++) { for (int j = 0; j < N - i - 1; j++) printf(" "); for (int j = 0; j < 2 * i + 1; j++) printf("*"); printf("\n"); } for (int i = 1; i < N; i++..

백준 온라인 저지(BOJ) 2443번 문제https://www.acmicpc.net/problem/2443 1. 문제 요약첫째 줄에 별 2*N-1개, 둘째 줄에 별 2*N-3개, ... N번째 줄에 별 1개 찍기2442번과 마찬가지로 별은 가운데를 기준으로 대칭이어야 하며, 별 뒤에는 공백이 없어야 하는듯? 2. 알고리즘for문 안의 수들의 살짝 복잡한데, 더 간단하게 쓰는 법이 있겠지만 일단 빨리 푸느라 대충 씀. 3. 코드 #include using namespace std; int main() { int N; scanf("%d", &N); for (int i = 0; i < N; i++) { for (int j = 0; j < i; j++) printf(" "); for (int j = 0; j <..

백준 온라인 저지(BOJ) 2442번 문제 https://www.acmicpc.net/problem/2442 1. 문제 요약 첫째 줄에 별 1개, 둘째 줄에 별 3개, ... N번째 줄에 별 2*N-1개 찍기 별은 가운데를 기준으로 대칭이어야 하며, 별 뒤에는 공백이 없어야 하는듯? 2. 알고리즘 여기서부터 살짝 복잡한 기미가 보이지만, 아직은 개수만 헷갈리지 않는다면 푸는 데 크게 무리는 없다. 3. 코드 #include using namespace std; int main() { int N; scanf("%d", &N); for (int i = 0; i < N; i++) { for (int j = 0; j < N - i - 1; j++) printf(" "); for (int j = 0; j < 2 ..

백준 온라인 저지(BOJ) 2441번 문제 https://www.acmicpc.net/problem/2441 1. 문제 요약 첫째 줄에 별 N개, 둘째 줄에 별 N-1개, ... N번째 줄에 별 1개 찍기 (오른쪽 정렬로) 2. 알고리즘 생략 3. 코드 #include using namespace std; int main() { int N; scanf("%d", &N); for (int i = 0; i < N; i++) { for (int j = 0; j < i; j++) printf(" "); for (int j = 0; j < N - i; j++) printf("*"); printf("\n"); } return 0; }

백준 온라인 저지(BOJ) 2440번 문제 https://www.acmicpc.net/problem/2440 1. 문제 요약 첫째 줄에 별 N개, 둘째 줄에 별 N-1개, ... N번째 줄에 별 1개 찍기 2. 알고리즘 생략 3. 코드 #include using namespace std; int main() { int N; scanf("%d", &N); for (int i = 0; i < N; i++) { for (int j = 0; j < N - i ; j++) printf("*"); printf("\n"); } return 0; }

백준 온라인 저지(BOJ) 2439번 문제 https://www.acmicpc.net/problem/2439 1. 문제 요약 첫째 줄에 별 1개, 둘째 줄에 별 2개, ... N번째 줄에 별 N개 찍기 (오른쪽 정렬로) 2. 알고리즘 빈 공간에 개수에 맞추어 공백을 삽입하자. 3. 코드 #include using namespace std; int main() { int N; scanf("%d", &N); for (int i = 1; i

백준 온라인 저지(BOJ) 1076번 문제https://www.acmicpc.net/problem/1076 1. 문제 요약10종류의 색깔마다 값, 곱이 정해져있다.3개의 색깔을 보고 저항의 값을 출력해야 하는데,첫 번째 색은 십의 자리, 두 번째는 일의 자리, 세 번째는 곱을 나타낸다. 2. 알고리즘글자를 읽어 비교해야 하므로, string이나 cstring을 사용하면 편리하다.C++이므로 string을 사용하도록 하자.읽은 값을 길이 3짜리 배열에 저장하고, 값을 계산해서 출력한다.가장 큰 경우는 white, white, white인 경우인데 이 경우 값이 990억이므로 int 대신 long long을 사용하면 수월하다. 3. 코드 #include #include using namespace std; ..