문제

코드

#include <stdio.h>

int main() {
	int a, b, c, a1, cnt=0;
	scanf("%d", &a);
	a1 = a;
	while (1) {
		if (a >= 10) {
			b = a / 10 + a % 10;
			if (b >= 10) {
				c = (a % 10) * 10 + (b % 10);
			}
			else c = (a % 10) * 10 + b;
		}
		else {
			c = a * 11;
		}
		cnt += 1;
		if (a1 == c) {
			printf("%d", cnt);
			break;
		}
		else {
			a = c;
		}
	}
}

문제

https://www.acmicpc.net/problem/1107

코드

import sys
input=sys.stdin.readline

channel=int(input())
n=int(input())
broken=list(map(int, input().split()))

count=abs(100-channel)

for i in range(1000001):
    i=str(i)
    for j in range(len(i)):
        if int(i[j]) in broken: break
        elif j==len(i)-1:
            count=min(count, abs(int(i)-channel)+len(i))

print(count)

문제 해결

처음 이문제를 보았을때 어떻게 풀어야 할지 고민했었다. 풀이 방법은 '브루트포스알고리즘' 이다.

여기서 range를 N의 최대 범위인 500,000이 아닌 그 두 배 1,000,000로 해준 것은, 수빈이가 이동하려는 채널의 범위는 500,000 이하이지만 채널 자체는 무한대라는 점 때문이다.

따라서, target와 가장 가까운 숫자를 찾을 때 target보다 작은 값은 물론이고 target보다 큰 값도 찾아줘야하고, 이 값은 500,000 이상도 가능하다.

만약에 수빈이가 이동하려는 채널이 500,000이고, 리모컨의 숫자 중 1, 2, 3, 4, 5가 고장났다고 가정하자.

이 때, range의 범위가 500,000으로 제한되면, 시작점인 100번에서 +만 눌러서 500,000까지 도달하는 총 499,900번 버튼을 클릭하게 할 것이다.

하지만 물론 이것은 최적의 해가 아니다.

600,000에서 -를 100,000번 눌러 target에 도달하는 것이 최적의 해일 것이다.

이러한 이유 때문에 range는 1,000,000까지로 설정해주어야 한다.

문제

https://www.acmicpc.net/problem/1065

#include <stdio.h>
int checkhansu(int n);

int main() {
	int n, cnt1=0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		if (checkhansu(i) == 1) {
			cnt1+=1;
		}
	}
	printf("%d", cnt1);
}
int checkhansu(int n){
	if (n < 100){
		return 1;
	}
	else {
		int cnt = 0, p[1000] = {0}, tmp;
		while (n > 0) {
			p[cnt++] = n % 10;
			n /= 10;
		}
		int d = p[cnt - 1] - p[cnt - 2];
		for (int i = cnt - 2; i >= 1; i--) {
			if (d != (p[i] - p[i - 1])) return 0;
		}
		return 1;
	}

문제 해결

100 미만의 정수는 모두 한수가 맞으므로 1을 리턴한다.

이후 주어진  수를 자릿 수마다 분리하여 배열에 저장한다.

이후 각 자릿수가 등차수열 인지 확인

맞다면 1 리턴, 아니라면 0 리턴

브루트포스 알고리즘으로 그냥 무난하게 짜실수 있을 것이다.

문제

https://www.acmicpc.net/problem/1012

코드

import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline

def dfs(x,y):
    if 0>x or y<0 or x>=m or y>=n:
        return False
    if array[x][y]==1:
        array[x][y]=0
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y-1)
        dfs(x,y+1)
        return True    
    return False

T=int(input())
for l in range(T):
  cnt1=0
  m,n,k= map(int, input().split())
  array=[[0]*n for _ in range(m)]

  for j in range(k):
    x, y= map(int,input().split())
    array[x][y]=1
  
  for i in range(m):
    for j in range(n):
      if dfs(i,j)==True:
        cnt1+=1

  print(cnt1)

문제해결

기본적인 dfs/bfs 문제로 dfs로 풀었지만 bfs로도 해결가능하다.

본 문제에서의 함정은 x,y가 반대로 들어오기때문에 런타임 에러를 겪기도 하므로 실수를 주의해야한다.

또한 파이썬의 런타임 에러를 주의해야한다. 

recursion의 깊이가 너무 적게 지정되는 경우 재귀를 하다가 런타임 에러가 발생할 수 있으므로

코드 상단의 내용을 추가해주면 됩니다.