본문 바로가기

전체 목록!291

[BOJ] 3049번: 다각형의 대각선 3049번: 다각형의 대각선 대각선 교차점 하나가 생기려면 대각선 두 개가 필요하고 대각선은 꼭지점 2개로 이뤄지기 때문에 총 4개의 꼭지점의 조합이 필요하다. 즉, n개의 꼭지점 개수 중에서 4개를 순서 없이 선택하면 된다. 그래서 를 계산하면 된다. 코드 #include int main() { int n; scanf("%d", &n); printf("%d", (n * (n - 1) * (n - 2) * (n - 3)) / 24); return 0; } 2018. 7. 19.
천코대 2회 예선 한탄, 자괴감 풀이는 출제자이자 존경스러운 욱제 선배님의 블로그를 참조하시면 될 것 같습니다. 링크 팀은 1학년 후배, 반 친구, 그리고 나로 구성해서 나갔다. 솔직히 팀원 애들 실력을 몰라서 정올 본선 초등부 문제 풀면서 연습해보라 했다. 뭐 굉장히 쉽게 5번까지 AC를 받았단다. 그래서 나는 속으로 학교 정올반 소속인 내가 가장 적게 푸는 거 아닌가 싶었지만 어제 예선을 한 결과 우리 팀 중에 나 빼곤 한 명도 못 풀었더라...물론 나도 한 문제 밖에 못 풀었다. 2개 정도는 더 풀 수 있었는데 시간이 부족했다. 무엇보다 트라이를 하면 할 수록 멘탈이 나가서 막판에는 이성을 잃은 것 같다 ㄹㅇ ㅋㅋㅋㅋㅋ결국 예선 조차 붙지 못하고 떨어졌는데 역시 나는 너무 공부를 안 했다는 것을 몸소 체험했다. 여태까지는 해야지 .. 2018. 7. 14.
[BOJ] 2587번: 대표값2 2587번: 대표값2 풀이 5개로 고정되어 있는 자연수가 주어지기 때문에 중앙값은 정렬 후에 v[2]가 된다. 코드 #include using namespace std; vector v; int sum = 0; int main() { cin.tie(0); ios_base::sync_with_stdio(false); for (int i = 0, a; i > a; sum += a; v.push_back(a); } sort(v.begin(), v.end()); cout 2018. 7. 13.
[BOJ] 2588번: 곱셈 2588번: 곱셈 풀이 ㅁㄴㅇㄹ... 간단하게 생각하자. 코드 #include using namespace std; int main() { ios_base::sync_with_stdio(false), cin.tie(0); int n1, n2; scanf("%d %d", &n1, &n2); printf("%d\n%d\n%d\n%d", n2 % 10 * n1, n2 % 100 / 10 * n1, n2 / 100 * n1, n1 * n2); return 0; } 2018. 7. 13.
[BOJ] 2609번: 최대공약수와 최소공배수 2609번: 최대공약수와 최소공배수 풀이 gcd, lcm코드 정도는 외워놓으면 좋다. 구현하는 것이 문제이기 때문에 어려운 것은 없었다. 코드 #include using namespace std; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int lcm(int a, int b, int c) { return a * (b / c); } int main() { cin.tie(0); ios_base::sync_with_stdio(false); int a, b; cin >> a >> b; int tmp = gcd(a, b); cout 2018. 7. 13.
[BOJ] 10800번: 컬러볼 10800번: 컬러볼 풀이 지역본선 2015에서 초등부 4번, 고등부 2번으로 나왔던 문제다. 예전에 한 번 풀어본 적이 있었는데 무식하게 으로 풀었다가 당연히 시간 초과를 맞았다 ㅋㅋ 우선 이건 내 머리에서 나온 풀이가 아니다. 사이즈 별로 정렬하는 것까진 생각했는데 색을 어떻게 처리해야 할 지 몰랐다. (왜 그랬는지 모르겠다) CODER's BRUNCH님 블로그 그래도 지금은 완전히 이해했으니 정리하는 겸 써보겠다... N ball[j].s; ++j) { accul += ball[j].s; colorSum[ball[j].c] += ball[j].s; } ret[ball[i].idx] = accul - colorSum[ball[i].c]; } for (int i = 0; i < N; ++i) print.. 2018. 7. 13.
[BOJ] 2589번: 보물섬 2589번: 보물섬 풀이 BFS로 맵을 다 돌아주면 된다. 최댓값을 찾아야 하기 때문에 시작점을 바꿔가면서 BFS 돌린다. 참고로 Max - 1을 결과로 출력해야 하는데 -1을 하는 이유는 visit_y_x= 1을 항상 하기 때문에 원하는 결과 값보다 항상 +1이 되기 때문이다. 코드 #include using namespace std; int w, h; char Map[51][51] = { 0, }; int BFS(int y, int x) { int MAX = 0; int visit[51][51] = { 0, }; const int dx[] = {0, -1, 1, 0}; const int dy[] = {-1, 0, 0, 1}; queue q; q.push(make_pair(y, x)); visit[y].. 2018. 7. 13.
[BOJ] 2608번: 로마 숫자 2608번: 로마 숫자 어렵다고 생각했는데 어떻게 변수를 잘 저장하고 사용하느냐를 물어보는 듯한 문제였다. token[][3] = {"IV", "XL", "CD", "M"}; 이렇게 저장하는 게 핵심이었던 것 같다. 코드 #include using namespace std; char s[11], token[][3] = {"IV", "XL", "CD", "M"}; // 4, 40, 400, 1000 int roman[90], ans = 0; const int divs = 1000, zerocnt = 3; int main() { cin.tie(0); ios_base::sync_with_stdio(false); roman['I'] = 1, roman['V'] = 5, roman['X'] = 10, roman[.. 2018. 7. 12.
[BOJ] 2607번: 비슷한 단어 2607번: 비슷한 단어 문제 요약 조건에 따라 첫 번째 단어와 비슷한 단어의 개수를 출력한다. 조건 같은 구성이란: 두 단어가 같은 종류의 문자로 이루어져 있다. 같은 문자는 같은 개수만큼 있다. 같은 종류의 문자가 같은 개수만큼 있거나, 한 단어에서 문자를 더하거나 빼거나 한 문자를 다른 문자로 바꾸거나 해서 같은 구성을 만들면 비슷한 단어로 취급한다. 단어의 변형을 한 번만 할 수 있기 때문에 단어의 길이 차이가 1 이하여야 한다. 그리고 문자 차이가 2개 이하여야 한다. BOJ, BOI 두 단어가 있을 때, 문자의 차이는 2개다. 그렇지만 I를 J로 바꿔주면 비슷한 단어가 된다. 코드 #include using namespace std; int n, ans = 0; bool check(const .. 2018. 7. 12.
[BOJ] 11048번: 이동하기 11048번: 이동하기 풀이 간단히 바로 생각나는 점화식은 dp[i][j]=max(dp[i−1][j],dp[i−1][j−1],dp[i][j−1])dp[i][j] = max(dp[i - 1][j], dp[i - 1][j-1], dp[i][j-1])dp[i][j]=max(dp[i−1][j],dp[i−1][j−1],dp[i][j−1])인데 캔디 개수로 음수가 나올리가 없으므로 dp[i−1][j−1]dp[i-1][j-1]dp[i−1][j−1]을 도는 것은 사치다. 최대한 많이 얻어야 좋은 건데 바로 한 단계를 건너뛰는 것은 엄연한 사치다. 그래서 dp[i][j]=max(dp[i−1][j],dp[i][j−1])dp[i][j] = max(dp[i - 1][j], dp[i][j-1])dp[i][j]=max(dp[i−.. 2018. 6. 4.
[BOJ] 1932번: 정수 삼각형 1932번: 정수 삼각형 풀이 현재 칸을 기준으로 이전 칸에서 좌, 우를 비교해서 최댓값을 계속 축적해주면 된다. 그리고 마지막 줄을 순회하면서 최댓값을 구하는 방법. 코드 예전에 짠 코드 #include const int MAX = 501; int N, max = -1, i, j; int v[MAX][MAX]; void input() { scanf("%d", &N); for (int i = 1; i 2018. 6. 4.
[BOJ] 11057번: 오르막 수 11057번: 오르막 수 풀이 우선 본 문제의 아이디어는 쉬운 계단 수에서 가져왔다. 굉장히 유사한 방법(거의 똑같다)으로 풀 수 있었다. D[i][j]는 길이가 i이고 끝자리 숫자가 j인 오르막 수 따라서 i - 1 길이, 끝자리 숫자가 현재 j보다 작은 오르막 수들의 경우의 수를 누적 시키면 된다. 코드 #include int n, D[1001][10]; const int div = 10007; int main() { scanf("%d", &n); for (int i = 0; i 2018. 6. 3.
[BOJ] 1010번: 다리 놓기 1010번: 다리 놓기 풀이 문제 읽을 때부터 뭔가 조합의 느낌이 났는데 조합이었다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 그래서 nCr을 구현해주면 된다. 코드 #include #include int n, r, D[31][31]; long long int nCr(int n, int r) { if (n == r || r == 0) return D[n][r] = 1; if (r == 1) return D[n][r] = n; if (D[n][r]) return D[n][r]; return D[n][r] = (nCr(n - 1, r - 1) + nCr(n - 1, r)); } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d %d", &n, &r); printf.. 2018. 6. 3.
[BOJ] 2163번: 초콜릿 자르기 2163번: 초콜릿 자르기 풀이 감이 안 잡혔는데 그냥 우리가 실제로 초콜릿을 쪼갤 때를 생각하면 된다. 보통 반으로 계속 쪼개지 않는가? 그걸 생각하며 관계식을 세우면 된다. 가로로 반으로 쪼갤 때 or 세로로 반으로 쪼갤 때 중 최솟값을 구하면 된다. 코드 #include #include int D[301][301], N, M; int f(int n, int m) { // 종료 조건 if (n == 1) return D[n][m] = m - 1; else if (m == 1) return D[n][m] = n - 1; return D[n][m] = std::min(n * f(1, m) + (n - 1), m * f(n, 1) + (m - 1)); } int main() { scanf("%d %d", .. 2018. 6. 2.
[BOJ] 5622번: 다이얼 5622번: 다이얼 풀이 알파벳마다 걸리는 시간을 주면 된다. 코드 #include char s[16]; int sum = 0, t[] = {3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10}; int main() { scanf("%s", &s); for (char *i = s; *i; ++i) { sum += t[*i - 'A']; } printf("%d\n", sum); return 0; } 2018. 6. 2.

티스토리툴바