파게로그

문제 링크: 1436번 영화감독 숌 https://www.acmicpc.net/problem/1436 처음에 cnt를 0으로 시작할지 1로 시작할지 헷갈렸다. 차근차근 생각하자! #include #include #define INF 1000000000 using namespace std; int main(void) { /* input */ int n; cin >> n; int answer; /* increase number */ int cnt = 0; // 6이 연속으로 3번 나오는 수의 개수 string st; int cnt6 = 0; // 숫자 내에서 연속으로 나오는 3의 개수 bool flag; for (int i = 666; i 2) { flag = true; break; } } else { //..

문제 링크: 1018번 체스판 다시 칠하기 https://www.acmicpc.net/problem/1018 체스판과 같은 크기로, 2차원 int 배열을 먼저 다음과 같이 2개 더 만든다. B로 시작하는 체스판, W로 시작하는 체스판에 대해서 각각의 칸에, 다시 칠해야 할 때 1, 다시 칠하지 않아도 될 때 0을 넣는다. 가로 8칸, 세로 8칸을 잘라낼 때 기준은 좌상단 모서리의 좌표로 설정했다. 이 좌표, 즉 board[row][col]의 row, col의 범위는 0

문제 링크: 7568번 덩치 https://www.acmicpc.net/problem/7568 모든 경우를 일일이 탐색하는 문제였는데 조금 빠른 속도를 내보겠다고 잘못된 선택을 했다. 처음에 시도한 방식은 다음과 같다. 에서 x+y를 통해 정렬한 후 위아래로 2개씩 비교하면서 덩치 등수를 크게 하거나, 그대로 두었다. 하지만 다음과 같은 반례가 존재한다. , , , 과 같은 경우에는 정렬 여부에 따라서 덩치 등수가 달라진다. 올바른 풀이는 다음과 같다. #include using namespace std; int main(void) { // declare int n; cin >> n; int *xarr = (int *)(malloc(sizeof(int)*n)); int *yarr = (int *)(mal..

문제 링크: 2168번 타일 위의 대각선 https://www.acmicpc.net/problem/2168 가로 길이를 x, 세로 길이를 y라 하고 GCD(x, y) = G라 하면, x = GX, y = GY와 같이 표현할 수 있다. 이 때 대각선의 기울기는 y/x = GY/GX = Y/X이고, 가로로 X칸, 세로로 Y칸 이동할 때마다 타일의 경계점과 만난다. 대각선 위에 X*Y의 사각형은 G개 있고, 대각선을 우하향으로 그린다고 할 때 그려진 타일은 반드시 왼쪽 상단에서 우측 하단으로 한 칸씩 이동하므로 각 사각형마다 x+y-1개의 타일에 대각선이 지나간다. 따라서 대각선이 그려져 있는 타일의 개수는 G*(X+Y-1)개이다. 여기서 최대공약수를 빨리 구하는 방법을 헤맸는데 유클리드 호제법을 떠올려야 한..

문제 링크: 11729번 하노이 탑 이동 순서 https://www.acmicpc.net/problem/11729 from, mid, to가 있을 때, n개를 from에서 to로 옮기기 위해서는... 1. n-1개를 from에서 mid로 옮긴다. 2. 1개를 from에서 to로 옮긴다. 3. n-1개를 mid에서 to로 옮긴다. 이런 아이디어를 기본으로 생각하면 되는 것 같다. def hanoi(n, f, m, t, arr): if n==1: arr[0] += 1 arr.append("{f} {t}".format(f=f, t=t)) return hanoi(n-1, f, t, m, arr) hanoi(1, f, m, t, arr) hanoi(n-1, m, f, t, arr) return n = int(in..

문제 링크: 2447번 별 찍기 10 https://www.acmicpc.net/problem/2447 재귀는 어렵다. 하지만 피할 수 없기에 즐겨야(?) 한다. 프랙탈이 모니터를 채울 때의 그 쾌감을...! 배열을 사용하면 '비교적' 쉽게 해결할 수 있는 문제이다. 다른 풀이를 보니까, 엄청 큰 2차원 배열을 미리 선언해놓고 인덱스를 통해 채워나가는 풀이도 있다. def paint(n): if n==1: return ['*'] arr = [0 for i in range(n)] prev = n//3 prevArr = paint(prev) idx = 0 for i in range(3): for j in range(prev): if i == 1: arr[idx] = prevArr[j]+' '*prev+pre..

문제 링크: 백준 10870번 피보나치 수 5 https://www.acmicpc.net/problem/10870 DP 없이 피보나치 수 느리게 구하기! def fibo(n): if n==0: return 0 if n==1: return 1 return fibo(n-1)+fibo(n-2) n = int(input()) print(fibo(n))

문제 링크: 백준 10872번 팩토리얼 https://www.acmicpc.net/problem/10872 재귀 문제는 무조건 다 풀이를 남기기로 한다. 그리고, 아리스토텔레스의 체에서 1의 경우와 마찬가지로 팩토리얼 또한 0! = 1임을 누락시키지 않도록 하자. def factorial(n): if n in [0, 1]: return 1 return n*factorial(n-1) n = int(input()) print(factorial(n))