목록PS/백준 온라인 저지 (82)
The Way
백준 온라인 저지(BOJ) 2178번 문제https://www.acmicpc.net/problem/2178 1. 문제 요약미로의 첫 블럭에서 지정된 블럭까지 가는 데 최소 소요 칸 수 구하기 2. 알고리즘가장 기본적인 BFS 문제이다.최종 구하려는 블럭의 depth값을 출력하면 된다.큐에 저장해줄 때는 i * 100 + j의 값을 사용하였다. 3. 코드 #include #include int main() { char maze[100][100]; int depth[100][100]; int N, M; scanf("%d %d", &N, &M); for (int i = 0; i < N; ++i) scanf("%s", maze[i]); int d = 1; maze[0][0] = '0'; depth[0][0] =..
백준 온라인 저지(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; }