본문 바로가기
반응형

PS 문제 풀이/Baekjoon446

[BOJ] 백준 1987 알파벳 출처: https://www.acmicpc.net/problem/1987 Input 2 4 CAAB ADCB Output 3 서로 다른 알파벳으로 이루어진 최대 경로 같은 알파벳이 적힌 칸을 두 번 지나갈 수 없는 조건을 확인하기 위해 visited[26]을 사용하지 않고 비트마스크 활용 ex) 0 00000 00000 00000 00000 00011 → BA ex) 1 00000 00000 00000 00000 00101 → ZCA #include using namespace std; #define MAX 20 int R, C, answer; string board[MAX]; int dx[] = { 0, 0, 1, -1 }; int dy[] = { 1, -1, 0, 0 }; void DFS(int x,.. 2021. 2. 20.
[BOJ] 백준 3987 보이저 1호 출처: https://www.acmicpc.net/problem/3987 Input 5 5 ../.\ ..... .C... ...C. \.../ 3 3 Output U 17 문제 조건 중 같은 시간일 경우 U, R, D, L의 순서 중 앞서는 것을 출력해야 하므로 U → R → D → L 순서대로 시뮬레이션 해서 신호 전달횟수가 커지는 경우만 갱신 시그널이 항성계 내에 무한히 존재할 수 있는 경우가 있다고 하는데, 행성 배치에 따라서 동일한 지점을 다른 방향으로 접근할 수 있는데 이전에 들렸던 위치를 다시 방문했을 때, 그때의 시그널의 방향과 현재의 시그널의 방향이 같은 경우에 특정 구간을 무한히 전파되는것으로 간주할 수 있습니다. bool visited[x][y][dir] = (x, y) 지점을 dir.. 2021. 2. 20.
[BOJ] 백준 1339 단어 수학 출처: https://www.acmicpc.net/problem/1339 Input 2 AAA AAA Output 1998 A와 B 중 어떤 알파벳에 9를 부여할 지 고민해보아야 합니다. Input 2 ABC BCD Output 1866 ABC → 100A + 10B + C BCD → 100B + 10C + D ▶ ABC + BCD = 100A + 110B + 10C + D A, B, C, D를 미지수로 생각하고 계수를 기준으로 정렬하며 다음과 같습니다. 110B + 100A + 10C + D → B = 9, A = 8, C = 7, D = 6 대문자 알파벳 26개가 존재하므로 다음과 같이 설정 int alphabet[26] = 알파벳 계수 ex) ABC + BCD = 100A + 110B + 10C +.. 2021. 2. 20.
[BOJ] 백준 5585 거스름돈 출처: https://www.acmicpc.net/problem/5585 Input 380 Output 4 500원을 거슬러 받을 때, 100원 짜리 5개가 아닌 500원 짜리 1개를 돌려받습니다. 즉, 거스름돈 동전개수가 최소가 되어야 합니다. ▶ 큰 동전단위부터 최대한 거슬러주면서 잔돈이 0원이 되게합니다. #include using namespace std; int coin[] = {500, 100, 50, 10, 5, 1}; int change, coinCnt; int findMaxCnt(int idx){ int cnt = 0; while(true){ if(change < coin[idx] * cnt){ cnt--; break; } cnt++; } return cnt; } int main() { .. 2021. 2. 20.
[BOJ] 백준 3053 택시 기하학 출처: https://www.acmicpc.net/problem/3053 Input 1 Output 3.141593 2.000000 유클리드 기하학에서의 거리는 다음과 같습니다. 원의 정의는 동일하므로 다음과 같이 그릴 수 있습니다. 결국, 유클리드 기하학에서 원의 공식은 π × r2 이며, 택시 기하학에서는 정가형의 넓이를 구하면 됩니다. → 한 변의 길이 × 한 변의 길이 = 정사각형 넓이 주어지는 반지름의 길이 = a라고 했을 때, 정사각형의 넓이 2 × a2 #include #include #include using namespace std; int main() { int r; cin >> r; printf("%f\n", M_PI * pow(r, 2)); printf("%f\n", 2 * (pow.. 2021. 2. 20.
[BOJ] 백준 14916 거스름돈 출처: https://www.acmicpc.net/problem/14916 Input Output 거스름돈을 2원과 5원을 활용하여 최대한 적은 수의 동전으로 거슬러주는 방법을 구하는 문제 문제 조건상 (1 2021. 2. 20.
[BOJ] 백준 1614 영식이의 손가락 출처: https://www.acmicpc.net/problem/1614 Input 2 3 Output 15 [Test Case 분석] 엄지→ 검지 → 중지 → 약지 → 새끼 약지 → 중지 → 검지 → 엄지 → 검지 중지 → 약지 → 새끼 → 약지 → 중지 → 검지 ▶ 총 15회 [아픈 손가락 별 규칙성] 1. 엄지 : 0, 8, 16, 24, 32, 40, 48 → 8 증가 2. 검지 : 1, 7, 9, 15, 17, 23, 25 → 6 증가, 2 증가 3. 중지 : 2, 6, 10, 14, 18, 22, 26 → 4 증가 4. 약지 : 3, 5, 11, 13, 19, 21, 29 → 2 증가, 6 증가 5. 새끼 : 4, 12, 20, 28, 36, 44 → 8 증가 ▶ 받은 수가 n, m인 경우 -.. 2021. 2. 20.
[BOJ] 백준 1009 분산처리 출처: https://www.acmicpc.net/problem/1009 Input 5 1 6 3 7 6 2 7 100 9 635 Output 1 7 6 1 9 주먹구구 방식으로 구해봐야 1001000000 결과 자체를 저장하는 것은 쉽지 않습니다. 62 : 6 × 6 = 36 → 6번째 컴퓨터가 마지막 데이터 처리 75 : 7 × 7 × 7 × 7 × 7 = 16,807 → 7번째 컴퓨터가 마지막 데이터 처리 84 : 8 × 8 × 8 × 8 = 4,096 → 6번째 컴퓨터가 마지막 데이터 처리 ▶ 곱해지는 결과에서 1의 자리가 무엇인지 중요합니다. ← 나머지 연산(%) 이용 숫자 저장자체는 가능해졌지만 연산 속도를 무시할 수는 없습니다. ※ 거듭 곱해지면서 1의 자릿수 변화 1: 1 → 1 → 1 →.. 2021. 2. 20.
[BOJ] 백준 1850 최대 공약수 출처: https://www.acmicpc.net/problem/1850 Input 500000000000000000 500000000000000002 Output 11 ① A, B의 최대공약수를 구합니다. ex) GCD(3, 4) = 1 ex) GCD(3, 6) = 3 ② 위에서 구한 최대공약수 만큼 『 1 』 출력 #include using namespace std; long long GCD(long long a, long long b) { if (a % b == 0) return b; return GCD(b, a%b); } int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); long long a, b; c.. 2021. 2. 20.
[BOJ] 백준 1920 수 찾기 출처: https://www.acmicpc.net/problem/1920 Approach N, M이 작지 않은 숫자이기 때문에 배열을 한개씩 탐색하면 TLE 발생 Binary Search (이분 탐색) Binary Search (이분 탐색) Binary Search (이분 탐색) 정렬된 자료에서 목표값을 찾고자 할 때, 사용되는 탐색기법 O(logN) 리스트 중간의 값(mid)을 선택하여 찾고자 하는 값과 비교하는 방식 분할 정복 알고리즘(Divide and Conquer Al zoosso.tistory.com #include #include #include using namespace std; int N, M, temp, x; vector vec; int binarySearch(int left, int.. 2021. 2. 20.
반응형

티스토리툴바