본문 바로가기

온라인저지144

[BOJ] 2448번: 별찍기 - 11 2448번: 별찍기 - 11 풀이 분할&정복을 하면 된다. 큰 삼각형에서 3개로 삼분할 되는 프랙탈이 생기게 된다. 재귀함수를 사용해 삼분할에서 배열에 할당해주면 된다. 코드 #include #include int n; char arr[3072][6143]; void f(int n, int x, int y) { if (n == 3) { arr[y][x] = arr[y + 1][x - 1] = arr[y + 1][x + 1] = '*'; for (int i = 0; i > 1; f(dv, x, y); f(dv, x - dv, y + dv); f(dv, x + dv, y + dv); } int mai.. 2018. 5. 15.
[BOJ] 2523번: 별찍기 - 13 2523번: 별찍기 - 13 풀이 증가하는 삼각형 만들고 감소하는 삼각형 그려주면 된다. 코드 #include int main() { int n; scanf("%d", &n); for (int i = 0; i < n - 1; ++i, puts("")) { for (int j = 0; j = 0; --i, puts("")) { for (int j = 0; j 2018. 5. 15.
[BOJ] 2447번: 별찍기 - 10 2447번: 별찍기 - 10 풀이 규칙성을 찾는 수 밖에 없는데 대개 한 칸 빈칸은 쉽게 찾을 수 있을텐데 큰 빈칸을 찾는 게 어려울 수 있다. 이것은 표를 그려보면 쉽게 알 수 있는데 n=9일 때를 그려보면 '나누기 3의 몫’이 1인 구간만 빈칸인 것을 알 수 있다. 코드 #include int n; int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { int dx = i, dy = j; while (dx) { if (dx % 3 == 1 && dy % 3 == 1) break; dx /= 3, dy /= 3; } putchar(dx ? ' ' : '*'); } puts(""); } return .. 2018. 5. 15.
[BOJ] 1991번: 트리 순회 1991번: 트리 순회 풀이 입력이 알파벳 순서대로 주어진다. 재귀 함수를 잘 이용한다!(재귀 함수 안 쓰면 굉장히 귀찮아짐) 코드 #include #include // hint: these alphabet inputs are inputed as increasing sequence struct Node { int mValue; int mNextLeft; int mNextRight; }; struct Node arr[26]; char root, left, right; void PrintPreorder(int c); void PrintInorder(int c); void PrintPostorder(int c); int main() { int N; for (int i = 0; i < 26; ++i) { arr.. 2018. 5. 11.
[BOJ] 1009번: 분산처리 1009번: 분산처리풀이를 해주면 된다. 하지만 long long형도 100^1000000까지는 저장하지 못하기 때문에 그리고 우리의 목적에만 두자면 굳이 a^b를 계산한 후 %10을 할 필요가 없고 연산 중간마다 %10 연산을 해주면 된다.또한 단순히 반복문을 돌려서 계산해도 되지만 제곱의 성질인 을 이용하면 훨씬 더 빠른 연산이 가능하다. 이 연산에 대한 설명은 여기를 눌러서 확인하길 바란다.코드1234567891011121314151617181920212223#include int pow(int a, int b){ int ans = 1; while (b) { if (b & 1) ans = (ans * a) % 10; a = (a * a) % 10; b >>= 1; } return ans;} int .. 2018. 5. 5.
[BOJ] 4673번: 셀프 넘버 링크 : https://www.acmicpc.net/problem/4673 독해력이 딸려서 그런지... 사실 처음에 보고 이해를 못했다. 그러니 당연히 코드를 못 짰는데 어쨌든 d(N)은 N의 각 자릿수 합 + N이고 n을 d(n)의 생성자라고 한다. 33은 39의 생성자가 될 수 있는 건데 생성자들이 없는 수가 셀프 넘버다. 1, 3, 5, 7 ... 같은 수들인데 어떤 n으로도 d(n) = 1, 3, 5, 7 ... 을 만들어 낼 수 없다는 말이다. 그래서 난 10,000까지 반복문을 돌리면서 d(i)값을 배열 인덱스에 넣어줬다. (배열의 장점이 여기서 나올 수 있다...)지금보니 해쉬 비슷하게 생기긴 했다 ㅋㅋㅋ pseudo code로 볼때 array[d(i)] = true, if(array[i] .. 2018. 4. 24.
[BOJ] 14867번: 물통 14867번: 물통다른 친구가 우선 순위 큐를 이용해서 풀었다고 하고, 인터넷에 풀이 올리신 걸 보니 BFS or DFS로 푸시는 걸 보고 감이 안 잡혔다. ㅠㅠ아무튼 나는 1. A에서만 물통을 채워서 B에게 넘겨주는 작업, 2. B에서만 물통을 채워서 A에게 넘겨주는 작업. 이 둘 중에서 최소 작업 횟수를 출력하게 만들었다. 사실 코드가 굉장히 미개하다. 왜냐하면 중복이 너무 많기 때문이다... 코드를 짤 때 생각해야 할 점이 -1을 출력할 때인데 bucketA == a && bucketB == b일 때가 못 만들 때이다. 왜냐하면 이 때는 어짜피 bucketA, bucketB를 비워줘야 하는데 이렇게 되면 처음 시작할 때와 똑같은 상황이기 때문이다.또한 a == c && b == d일때는 2를 출력해.. 2018. 4. 9.
[BOJ] 14697번: 방 배정하기 14697번: 방 배정하기DP로도 풀어도 되고 범위가 굉장히 작기 때문에 Brute force로 풀어도 되는 문제이다.실력이 정말 부족하기 때문에 이런 Brute force 문제들도 많이 풀어 봐야겠다.12345678910111213141516171819202122232425262728#include using namespace std; int main(){ cin.sync_with_stdio(false), cout.sync_with_stdio(false); int b[3], n; for (int i = 0; i > b[i]; } cin >> n; for (int i = 0; i 2018. 4. 9.
[BOJ] 14696번: 딱지놀이 14969번: 딱지놀이 구현 문제다. 처음에 제출했을 때 틀려서 당황스러웠는데 알고보니 배열을 지역변수로 선언했기 때문에 쓰레기값이 있었던 것이였다. 변수의 초기화를 잘 해야 한다는 상식을 다시 상기 시켜준 문제이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include char chk(int Aar[], int Bar[]) { if (Aar[4] > Bar[4]) return 'A'; else if (Aar[4] Bar[3]) return 'A'; else if (Aar[3] Bar[2]) return 'A'; else if (Aar[2] Bar[1]) return.. 2018. 4. 9.
[BOJ] 13241번: 최소공배수 13241번: 최소공배수풀이gcd와 lcm을 알고 있으면 되는 문제다. 최소공배수는 주어진 정수 a, b에서 lcm(a, b) = a * b / gcd(a, b)이다.최대공약수는 유클리드 호제법을 사용하면 된다. 정수 m, n(m > n)이 주어질 때 gcd(m, n)은1234long long int gcd(long long int a, long long int b){ return b ? gcd(b, a % b) : a;} 다음과 같이 구현할 수 있다. 자세한 내용과 증명 과정은 링크를 참고하면 된다. 코드123456789101112131415161718192021#include long long int gcd(long long int a, long long int b){ return b ? gcd(b,.. 2018. 4. 1.
[BOJ] 11728번: 배열 합치기 11728번: 배열 합치기풀이한 배열에 다 받고 정렬, 출력!코드12345678910111213#include #include int A, B, Arr[2000001];int main(){ scanf("%d %d", &A, &B); A += B; for (int i = 0; i 2018. 3. 29.
[BOJ] 13866번: 팀 나누기 13866번: 팀 나누기풀이(1, 2), (3, 4) -> 비교(1, 3), (2, 4) -> 비교(1, 4), (2, 3) -> 비교코드123456789101112131415161718192021222324252627282930#include inline int min(int a, int b){ return a 0 ? a : -a;}int main(){ int ar[4]; for (int i = 0; i 2018. 3. 28.
[BOJ] 1912번: 연속합 1912: 연속합풀이dp[i] = max(dp[i - 1] + A[i], A[i])이다. (A[i]는 i번째 숫자이다.) 참고: i는 1부터 시작.점화식이 이렇게 나오는 이유는 문제가 "연속적"이라는데 중점을 두고 있기 때문이다. 코드sync_with_stdio(false)를 적용하면 scanf, printf보다 더 빠르다. 8ms, 12ms 12345678910111213141516171819202122232425#include using namespace std;const int mx = 100000 + 1;int n, A[mx], DP[mx]; inline int max(int a, int b) { return a > b ? a : b;}int main(){ cin.sync_with_stdio(fa.. 2018. 3. 28.
[BOJ] 2156: 포도주 시식 문제 링크설명dp[i]는 i번 것까지 먹었을 때 최댓값.현재 상태 i번째라고 했을 때 점화식 3개현재 것을 먹지 않았을 때 -> dp[i] = dp[i - 1] // i - 1 번째까지 마셨던 것을 업데이트이번 것만 먹을 때(1연속) -> dp[i] = glasses[i] + dp[i - 2] // i - 1 번은 분명히 마시지 않는다.i, i - 1번을 먹을 때(2연속) -> dp[i] = glasses[i] + glasses[i - 1] + dp[i - 3] // i - 2 번은 분명히 마시지 않는다.코드12345678910111213141516171819202122232425262728293031323334#include const int mn = 10001;inline int max(int a, .. 2018. 3. 26.
[BOJ] 1003번: 피보나치 함수 1003번: 피보나치 함수풀이그래프를 그려보면 0과 1이 호출될 때 일정한 규칙이 나오는 것을 알 수 있다. 그래서 dp[i][0]은 i번째 수에서 0의 호출 횟수이고 dp[i][1]은 i번째 수에서 1의 호출 횟수이다.또는 N이 주어질 때 dp[N]은 0의 호출 횟수이고 dp[N+1]은 1의 호출 횟수가 되는데 이 이유는 잘 모르겠다... (아시는 분은 알려주시면 정말 감사드리겠습니다!)코드1번째12345678910111213#include int main(){ int n, k; scanf("%d", &n); for (int j = 0; j 2018. 3. 25.

티스토리툴바