전체 글 292

[백준 BOJ] 1316 그룹 단어 체커

링크 https://www.acmicpc.net/problem/1316 풀이 같은 문자가 한 단어 내에서 떨어져서 존재하면 안 됩니다. 쭉 훑으면서 이미 나왔던 문자인지 체크하는 배열을 만들어 줍니다. 그 배열을 arr이라고 한다면 !arr[now] || now == before 일 때는 문제가 없겠죠? arr[now]++; before = now; 그럼 이렇게 처리해주시면 됩니다. 하지만 거짓이 나왔다면 반복문을 빠져나오고 count를 하지 않으면 됩니다. 코드 //1316_그룹 단어 체커 #include #include #include using namespace std; int n, flag, cnt, arr['z'+1]; string str; char before; int main() { scan..

PS/BOJ 2019.08.12

[백준 BOJ] 3052 나머지

링크 https://www.acmicpc.net/problem/3052 풀이 10개의 숫자가 입력되고 42로 나누었을 때, 서로 다른 나머지의 개수를 출력하는 문제입니다. 입력 받았을 때 arr[입력된 숫자 % 42]++; 이렇게 해주면 arr에 카운팅이 됩니다. 마지막에 카운팅 된 arr만 0~41까지 세어서 출력하면 됩니다. 코드 //3052_나머지 #include using namespace std; int tmp, arr[42], cnt; int main() { for(int i =1;i

PS/BOJ 2019.08.12

[백준 BOJ] 10757 큰 수 A+B

링크 https://www.acmicpc.net/problem/10757 풀이 숫자를 자릿수마다 배열에 담습니다. 반복문을 이용해서 한 자리씩 계산해줍니다. 여기서 carry bit를 만들어서 받아올림을 구현해줍니다. 마지막에 출력해줍니다. 코드 보고 이해하는 게 더 빠를 것 같아요! 이 방법은 carry, 즉 받아올림이 1이 넘지 않아서 쉽게 해결할 수 있습니다. 이를 응용하면 2의 n승을 빠르게 구할 수 있습니다. 코드 //10757_큰 수 A+B #include #include #include using namespace std; int a[10004], b[10004], sum[10004], carry; string str1, str2; int main() { cin >> str1 >> str2;..

PS/BOJ 2019.08.12

[백준 BOJ] 14490 백대열

링크 https://www.acmicpc.net/problem/14490 풀이 동아리 선배를 문제에서 만날 수 있어서 좋았던 문제입니다. n:m 받는 방법 -> scanf("%d:%d", &n, &m); gcd 함수를 정의해서 최대공약수를 구해줍니다. (유클리드 알고리즘) n과 m을 최대공약수로 나눈 수를 출력하면 됩니다. 코드 //14490_백대열 #include #include using namespace std; int n, m, res; int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a%b); } int main() { scanf("%d:%d", &n, &m); res = gcd(n, m); printf("%d:%d\n", n ..

PS/BOJ 2019.08.11

[백준 BOJ] 1074 Z

링크 https://www.acmicpc.net/problem/1074 풀이 Z가 많이 그려져 있습니다. 이렇게 $2^{n}$를 기준으로 4등분 해서 (r,c)가 어디 있는지 알아냅니다. 분할 정복 알고리즘으로 크게 4등분으로 쪼개고 더 잘게 잘게 쪼개가면서 답을 찾는 알고리즘입니다. 2 3 1이라는 입력 예제로 테스트 해보겠습니다. n이 2일 때, $2^{n}$는 2가 됩니다. r은 3이고 c는 1이기 때문에 r은 2보다 크거나 같고 c는 2보다 작은 3사분면이 해당됩니다. ans에는 $2\times 2^{n}$을 더하고, r과 c에는 $2^{n}$인 2로 나눈 나머지를 대입합니다. n이 1일 때, $2^{n}$는 1이 됩니다. r은 1이고 c는 1이기 때문에 r은 1보다 크거나 같고 c는 1보다 크거..

PS/BOJ 2019.08.11

[백준 BOJ] 1436 영화감독 숌

링크 https://www.acmicpc.net/problem/1436 풀이 6이 연속으로 3번 이상 들어간 수를 찾는 문제입니다. 1부터 시작해서 증가시키며 종말의 숫자를 찾으면 됩니다. 종말의 숫자를 찾는 방법은 다음과 같습니다. 예) 4666231 4666231%1000 -> 231 X 4666231/10 -> 466623 466623%1000 -> 623 X 466623/10 -> 46662 46662%1000 -> 662 X 46662/10 -> 4666 4666%1000 -> 666 O 찾았다!! 다음을 코드로 구현해서 count하고 그게 n과 같을 때 출력해주면 됩니다. 코드 //1436_영화감독 숌 #include #include using namespace std; int i, tmp, ..

PS/BOJ 2019.08.11

[백준 BOJ] 1018 체스판 다시 칠하기

링크 https://www.acmicpc.net/problem/1018 풀이 8*8짜리 부분을 선택하고 체스판으로 만들면 되는 문제입니다. n, m은 50이하이고 자른 체스판은 8*8이기 때문에 모든 수를 고려해도 50*50*8*8로 시간 초과가 나지 않습니다. (모든 수를 고려하는 걸 Brute-force 알고리즘이라고 합니다.) 자른 다음 저 위 두 사진처럼 만들면서 count를 해주면 되는데, 한 경우는 다른 경우의 64-count가 나오기 때문에 하나만 고려해도 됩니다. 칠하는 경우는 64가 최대이고, 그걸 고려해서 최소 경우를 찾아주면 됩니다. 색을 칠하는 방법은 홀홀과 짝짝은 같은 색, 홀짝과 짝홀은 같은 색이라는 것을 이용해서 (r%2)^(c%2) 이렇게 xor을 해줬습니다. 코드 //101..

PS/BOJ 2019.08.10
반응형