Tempo Tempo

BFS를 이용해, 시작 좌표부터 최종 좌표까지 도달하기위한 최소 시간을 구하는 문제이다. 시작 좌표로부터 그 다음 좌표로 이동하는 방법이 총 3가지 이다. 시작 좌표를 C라고 했을 때, (C - 1, C + 1, C * 2). 따라서 시작 정점으로부터 3개의 자식 노드를 가지는 트리 형식이라고 생각하고 풀이했다. 틀렸던 점들은 주석으로 표시해두는 방식을 채택했다. 각 2차원 배열들의 역할은 map -> 방문 여부 time -> 해당 좌표에 도달하기 위한 최소 시간 이다. 첫 번째 실수는 사소한 실수였고, 두 번째 실수가 엣지 케이스에대한 실수였다. 시작 지점이 0이 아닌 수이고, 도착 지점이 0이라면 항상 -1을 이용해 도착 지점에 도달해야 한다. 하지만 양수 범위만 생각한 나머지 cur - 1 > 0 ..

BFS를 이용해 문제를 풀이했다. dx, dy는 각 좌표로부터 이동할 변화량들을 가진 배열로, 익은 토마토가 다른 토마토들에게 영향을 끼칠 때의 좌표변화를위해 사용했다. 각 2차원 배열의 역할은, tomato -> 해당 토마토가 익었는가? 익었다면 1 map -> 해당 토마토가 익기까지 걸린 시간. 처음부터 익어있었다면 0 이다. 해당 문제를 풀다가 실수했었던 점은, "처음부터 익어있었던 토마토들의 좌표를 미리 Queue에 넣어두지 않았던 점"이다. 처음 좌표부터 모든 좌표를 돌며 토마토가 익어있을 경우 BFS를 돌리면, 가장 처음으로 나온 익은 토마토를 기준으로 걸린 시간이 미리 다 정해지기 때문이다. BFS는 어차피 Queue를 이용해 FIFO 형식으로 동작하므로, Queue [익은 토마토들의 좌표]..

문제 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 해당 경우의 수를 1,000,000,000로 나눈 나머지를 출력하시오. 문제설명 정수 K개를 더해서 N을 만들어야 한다. d[K][N] -> "K개의 정수를 이용해 N을 만들었다" 라고 생각하자. 점화식을 구하기 위해 이전 항을 생각해보면, 정수 한 개를 빼야 하므로 d[K - 1]\[N - ?]와 같이 나타낼 수 있다. ?는 여러가지 경우가 있기 때문에 답을 구하기 전에는 알 수 없는 값으로, 이러한 수들을 반복문을 이용해 찾아주어야 한다. 따라서 d[K][N] = sum(d..

문제 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다. 주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오. package backjoon; import java.io.*; public class Sum_of_power { public sta..

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 44267 26509 21036 59.311% 2 x n 직사각형을 1 x 2, 2 x 1, 2 x 2 타일로 채우는 경우의 수를 구하는 문제이다. 이렇게 여러가지 방법으로 경우의 수를 구할 때는 점화식을 이용해서 푸는게 일반적이다. 각 n에대해 2 x n 크기의 직사각형을 채우는 방법의 수가 들어있는 배열을 d라고하자. d[N]에대한 점화식을 구하기 위해 아래와 같은 과정이 필요하다. d[N - 1]의 값을 임의로 구했다고 했을 때, d[N - 1]을 구한 후에는 한 줄이 남으므로 1 . 2 x 1 타일 1개로 한 줄을 채우는 경우 한 가지이고, d[N - 2]의 값을 구했다고 하면 d[N - 2]를 구한 후에는 두 줄이 남으므..

Backjoon 10871번 X보다 작은 수 전체 코드 123456789101112131415161718#include#includeint main(){ int X,N,i,data=0,j; // X는 비교할 수 n은 입력받을 수의 갯수 i,j는 증가값, data는 배열 입력값 scanf("%d %d",&N,&X); int *A = (int *)malloc(sizeof(int)*N); for(i=0;i

Backjoon 1546번 평균 전체 코드 12345678910111213141516171819202122232425#include#includeint main(){ short N,i,j,k; // N은 받을 성적의 갯수(배열에 입력되는 자료의 갯수) i,j,k는 증가값 float result; // 성적을 처리한 후 평균을 구하기위해 합의 값을 저장할 변수 short testscore=0; // 각 성적을 배열에 넣을 때 임시로 값을 저장하는 변수 scanf("%hd",&N); short *test = (short *)malloc(sizeof(short)*N); for(i=0;i