본문 바로가기

Coding Test/백준(BOJ)

 (14)
[BOJ] 백준 #4673. 셀프 넘버 🎨 문제 문제 링크: https://www.acmicpc.net/problem/4673 알고리즘 분류: 수학, 구현, 브루트포스 난이도: Silver 5 💬 풀이 /////// L26에서 n과 d(n)이 비례하는 건 아니므로 if(n>MAX) break;를 하면 틀린다. 👉🏻 틀린 코드 확인 👩‍💻 코드 C++ #include using namespace std; #define MAX 10001 bool self_num[MAX]; int d(int n) { int res = n; int t = n; while(t) { res += t%10; t /= 10; } return res; } int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); fill_n..
[BOJ] 백준 #3985. 롤 케이크 🎨 문제 문제 링크: https://www.acmicpc.net/problem/3985 알고리즘 분류: 구현 난이도: Bronze 1 더보기 길이 L미터 짜리 롤케이크를 방청객 N명에게 나눠주려고 한다. 1번부터 N번까지의 방청객들은 차례대로 각각 원하는 조각을 범위 조각P부터~조각K까지 가져간다. 이때 이미 가져간 조각은 뒷사람이 원하더라도 받지 못한다. 가장 많은 조각을 원했던 방청객의 번호, 실제로 가장 많은 조각을 가져간 방청객의 번호를 구하는 문제다. 단, 답이 여러 개인 경우에는 번호가 작은 사람을 출력한다. 💬 풀이 👩‍💻 코드 C++ #include #include using namespace std; int cake[1001]; // 케이크 조각 별로 방청객 번호 int cnt[1001]..
[BOJ] 백준 #1543. 문서 검색 🎨 문제 문제 링크: https://www.acmicpc.net/problem/1543 알고리즘 분류: 문자열, 그리디 알고리즘, 브루트포스 난이도: Silver 4 💬 풀이 1. 입력에 공백이 포함되므로 getline()으로 입력받기 2. 브루트포스 L21에서 word[j-i]를 word[j]로 해놓고 맞왜틀🤦‍♀️ 인덱스 한번에 정확하게!!!! 주의!!!!! 헷갈리거나 실수할 것 같으면 종이에라도 그려보기 👩‍💻 코드 C++ #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); string s, word; getline(cin, s); getline(cin, word); int..
[BOJ] 백준 #1920. 수 찾기 (C++) 🎨 문제 문제 링크: https://www.acmicpc.net/problem/1920 알고리즘 분류: 이분 탐색 난이도: Silver 4 💬 풀이 N개의 수들을 배열에 담고, 정렬하여 이분탐색 실시 처음에는 N개의 수들을 벡터v에 담고, 단순히 선형탐색으로 했다가 시간초과 났었다. 👉🏻 틀린 코드 확인 그래서 이분탐색으로 했는데도, 이분탐색 함수 파라미터로 벡터 전체를 넘기니까 또 시간초과가 떴다. 👉🏻 틀린 코드 확인 그래서 벡터 크기를 동적으로 하지 않고 전역으로 뺀 다음 v(100001)을 할당했다. 이때 sort(v.begin(), v.end())가 아니라 i=0부터 i=N-1까지만 부분정렬을 해야 했는데, 할 줄 몰라서 틀렸다. (sort(v, v+N)은 안되더라.) 👉🏻 틀린 코드 확인 그래..
[BOJ] 백준 #1431. 시리얼 번호 (C++) 🎨 문제 문제 링크: https://www.acmicpc.net/problem/1431 알고리즘 분류: 정렬 난이도: Silver 3 💬 풀이 1. string을 여러 개 담은 vector, 즉 vector에 입력을 받고, 2. 문제 조건에 따라 cmp()를 정의해 sort해준다. 맞왜틀(맞는데 왜 자꾸 틀리다고 하지)을 한 945098번 하고 나서야 return s1> v[i]; } sort(v.begin(), v.end(), cmp); for (int i = 0; i < N; i++) { cout
[BOJ] 백준 #1026. 보물 (C++) 🎨 문제 문제 링크: https://www.acmicpc.net/problem/1026 알고리즘 분류: 수학, 그리디 알고리즘, 정렬 난이도: Silver 4 💬 풀이 A와 B를 각각 오름차순 정렬, 내림차순 정렬을 해준 뒤에 S += A[i] * B[i] 👩‍💻 코드 C++ #include #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int N; cin >> N; vector A(N), B(N); for (int i = 0; i > A[i]; } for (int i = 0; i > B[i]; } // 입력 so..
[BOJ] 백준 #1309. 동물원 (C++) 🎨 문제 문제 링크: https://www.acmicpc.net/problem/1309 알고리즘 분류: 다이나믹 프로그래밍 난이도: Silver 1 💬 풀이 처음에는 수학 조합문제 느낌으로 생각하다가, 노가다로 직접 N=1, N=2, N=3, ...일때 구하다가 DP 문제라고 삘이 왔다. 사실 내가 푼 방법은 N=1부터 N=4까지 노가다로 직접 값을 구한 뒤에, 그냥 끼워맞춰서 점화식을 구했다. 한마디로 야매로 풀었다는 것,,,ㅎㅎ 즉, 직접 dp[1]=3, dp[2]=7, dp[3]=17, dp[4]=41까지 구해놓은 다음에, 3,7,17,41,...에서 이전 항을 이용해서 숫자를 어떻게 하면 나올지 껴맞춰 보다가 일반화된 식 dp[n] = 2*dp[n-1] + dp[n-2]를 구할 수 있었다. 너무 ..
[BOJ] 백준 #2210. 숫자판 점프 (C++) 🎨 문제 문제 링크: https://www.acmicpc.net/problem/2210 알고리즘 분류: 깊이 우선 탐색 (DFS), 그래프 탐색, 브루트포스 난이도: Silver 2 💬 풀이 1. arr[5][5]에 숫자판을 입력받고, 2. 모든 좌표에 대해 DFS 경로 탐색 - 중복을 허용하지 않는 set을 이용한다. 👩‍💻 코드 C++ #define _CRT_SECURE_NO_WARNINGS #include #include #define N 5 using namespace std; int arr[N][N]; int dx[4] = { 1, 0, -1, 0 }; int dy[4] = { 0, 1, 0, -1 }; set s; void DFS(int y, int x, int n, int len) { if ..

티스토리툴바