본문 바로가기

온라인저지144

[BOJ] 3055번: 탈출 3055번: 탈출 BFS로 풀 수 있다. 주의해야 할 점은 물이 흐르는 것을 계산할 때 임시 배열에 변경 사항을 저장했다가 실제 배열에 적용시켜줘야 물이 정상적으로 흐르는 것을 계산할 수 있다. 코드 #include #include #include using namespace std; int R, C; const int dx[] = {0, 0, 1, -1}, dy[] = {-1, 1, 0, 0}; char map[51][51]; bool visit[51][51]; pair D, S; inline bool safe(int y, int x) { return (0 2018. 7. 19.
[BOJ] 3046번: R2 3046번: R2 R1과 평균 S가 주어지기 때문에 R2는 다음과 같이 구할 수 있다. 코드 #include int main() { int R1, S; scanf("%d %d", &R1, &S); printf("%d\n", 2 * S - R1); return 0; } 2018. 7. 19.
[BOJ] 3047번: ABC 3047번: ABC 숫자 3개를 정렬하면 쉽게 풀 수 있다. 코드 #include using namespace std; int main() { int al[3]; char str[4]; scanf("%d %d %d %s", &al[0], &al[1], &al[2], str); sort(al, al + 3); printf("%d %d %d", al[str[0] - 'A'], al[str[1] - 'A'], al[str[2] - 'A']); return 0; } 2018. 7. 19.
[BOJ] 3048번: 개미 3048번: 개미 단순히 구현을 통해 구할 수 있는 문제이기도 하고 결과를 생각해서 구현할 수도 있다. 하지만 나는 시뮬레이션을 다 돌렸다. 코드 시뮬레이션을 다 하기 때문에 결과를 기준으로 코드를 짠 것보다 메모리를 더 많이 사용한다. 더 느린진 모르겠지만 아마 더 느리지 않을까..? #include using namespace std; int main() { int N1, N2, T; array dir; string s1, s2; cin >> N1 >> N2 >> s1 >> s2 >> T; reverse(s1.begin(), s1.end()); for (int i = 0; i < N1; ++i) dir[i] = 'R'; for (int i = N1; i < N1 + N2; ++i) dir[i] = '.. 2018. 7. 19.
[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.
[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.

티스토리툴바