하루 코테 3문제풀기-2일차

하루에 3문제는 무리였나보다 ^-^..

004 숫자의 합 구하기(백준11660)

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

원래 숫자 리스트 A[i][j] 에서 배열에 대한 합 배열을 D[i][j] 인 배열을 만들어야한다.

합배열 공식

D[i][j] = D[i][j -1] + D[i -1][j] - D[i -1][j-1] + A[i][j]

예)
(1,2) 일 때, (1,1) (1,2) 을 더한 값이 합 배열에 들어간다.

합 배열 (1,4) 은 합 배열 (1,3) 과 리스트 배열의 (1,4) 합

합 배열 (3,4) 을 출력할려고 할 때,

합 배열 (2,4) + (3,3) 의 합 을 하고 중복 값 제거를 위해 - 리스트 배열(2,3) 제거 와 + 리스트 (3,4) 의 합이다. 

 

질의에 대한 답을 도출하기 위한 과정

구간 합 배열을 이용하기 전에 질의에 대한 답을 도출하기 위한 과정을 만들어야한다.

질의에서 2234 면
(2,2) (3,4) 으로 인식하고 

그러면, (3,1) (1,4) 부분을 빼주고 중복해서 빼준 값 (1,1) 값을 더해주면 된다.
질의 x1 y1 x2 y2 일때

D[x2][y2] - D[1][y2] - D[x2][1] + D[1][1]

 

코드 작성할 때,

n(리스트 크기) , m(질의 수)

A(원본 리스트), D(합 배열)

 

for n만큼 반복: 원본 리스트 데이터 저장

for i를 1부터 n까지 반복: 

합 배열 저장 
D[i][j] = D[i][j -1] + D[i -1][j] - D[i -1][j-1] + A[i][j]

for m만큼 반복 :

질의 대한 결과 계산 및 출력

D[x2][y2] - D[1][y2] - D[x2][1] + D[1][1]

 

코드 작성하기

package test.Num1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class 문제4 {
    public static void main(String[] args) throws IOException {
        //bufferReader로 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //받은 br 인스턴스를 String token으로 변환
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        //인덱스 0 부터 시작하는 걸 생각해서 만약 n = 3일 때, 4x4 값이 나오겠지?
        int A[][] = new int[n+1][n+1];
        //for 문을 이용하여 nxn 값 넣기
        for(int i=1; i<=n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //합배열 저장
        int D[][] = new int[n+1][n+1];
        for (int i = 1; i<=n; i++) {
            //구간의 합 구하기
            for (int j = 1; j <= n; j++) {
                D[i][j] = D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1] + A[i][j];
            }
        }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            int result = D[x2][y2] - D[x1 - 1][y2] - D[x2][y1 - 1]+ D[x1 - 1][y1 -1];
            System.out.println(result);
        }
    }
}

 

 

005숫자의 합 구하기(백준10986)

N개의 A1,A2,.. An 이 주어졌을 때 연속된 부분의 합이 M으로 나누어떨어지는 구간의 개수

연속된 부분의 합이 M으로 나누어 떨어진다. 

N 은 수의 개수 M 은 3으로 나누어 떨어지는 구간

1,2,3,1,2 라고 했을 때,  (1,2) (1,2,3) (1,2,3,1,2),(2,3,1)(3),(3,1,2),(1,2) 이 나온다

나머지를 계산할 때, ((1%3) + (2%3))% 3 은 (1+2)%3  와 동일하다.

 

우선 배열로 넣어보면, 일반 값이 들어있는
리스트A:

1

2

3

1

2

 

합 배열 S:

1

3

6

7

9

 

합 배열에 대한 %3 나머지 배열 :

1

0

0

1

0

 

나머지 배열에서 0이라고 되어 있는 애들은 바로 M 인 3을 나눠주면 0 이기 때문에 "경우의 수" 에 더해준다.

0의 나머지를 가진 애들은 3개 

나머지가 나오는 애들은 2개

 

나머지가 0으로 떨어지는 수 = 3개 
이제, 집중해서 봐야할 부분... ㅠ
구간을 선택할 때, 

나머지 배열에 이루어진 애들을 M으로 나누면 무조건 나머지는 0 이 나오는데,

예) 나머지배열 (s[4] - s[2] ) % 3 = 0

같은 나머지를 애들은 가지고 만든 구간의 합은 나머지가 0이 나온다.

총 나머지가 0 인 애들이 3개 이기 때문에 구간을 선택해야 하기 때문에 2개를 선택해야한다.
3개중에 2개 선택할 경우의 수 3C2  = 3C1 =  3개

1 은  2개가 있는데 그 중 2개를 선택해야하기 때문에, 2C2 로 식이 나온다. 즉, 경우의 수를  알아 낸다.  = 1개

 

는 총 7개 나온다.

슈도코드 작성하기

n 입력받기(수열의 개수)
m 입력받기(나누어떨어져야 하는 수)
A 입력받기(원본 수열 저장 리스트)
S 입력받기(합 배열)
C 입력받기(같은 나머지 인덱스를 카운트하는 리스트)
answer 선언하기 (정답 변수)

#합배열 저장 '배열의 합' 저장이기 때문에 1부터 시작한다
for i -> 1 ~ n-1
S[i] = S[i-1] + A[i]

#합배열을 나눈 나머지 값 0번째 배열부터 나누기 때문에 0부터 시작한다.
for i -> 0 ~ n-1
rem = S[i] % M 
if(rem == 0) : 
answer =+1

#C[rem]의 값을 1개 증가 

#C[i] (i가 나머지인 인덱스의 개수) 에서 2가지를 뽑는 경우의 수를 정답에 더하기
for i -> 0 ~ m-1 :
#C[i]개 중 2개를 뽑는 경우의 수 계산 공식 C[i] * (C[i]-1)/2

 

 

코드 작성하기

import sys
input = sys.stdin.readline
#split 사용하여 띄어쓰기 기준으로 나눠서 저장
# n 은 수열의 개수
n, m= map(int, input().split())
A = list(map(int, input().split()))
#0으로 초기화 하여 n 만큼 키울 것이다
S = [0] * n
# m은 나누어 떨어져야 하는 수
# C 은 같은 나머지의 들을 카운트하는 리스트 
C = [0] * m
answer = 0

S[0] = A[0]

#처음에 0번째 값은 0으로 넣어주자
#1번 인덱스부터 시작하도록 하자
for i in range (1, n) :
    S[i] = S[i-1] + A[i]

for i in range(n):
    remin = S[i] % m
    #만약에 나머지수가 0이 나올 경우 답의 경우 수 값을 1증가 시켜준다 
    if remin == 0 :
        answer += 1
    #remin 값을 인덱스로 넣고 그럼 배열의 인덱스는 0,1 밖에 안남을 것이다
    #거기서 나머지가 1인 애들이 3개가 생길 경우 인덱스 1은 3이 나올 것이다.
    C[remin] += 1

for i in range() :
    #C배열에 있는 수가 1이상인 것은 나머지가 같은 것이 여러 개 라는 것
    if C[i] > 1 :
        answer += ( C[i]*(C[i]-1) //2 )
print(answer)

 

 

이전에 풀었지만, 파이썬 언어로 다시 풀어보고 싶어서 가져온 브론즈 문제

 

001 숫자의 합 구하기(백준11720)

바로 코드 작성하기

#숫자의 개수
n = input()
#공백없이 주어지는 n개의 숫자들로 배열을 만든다
m = list(input())
sum = 0

#n개의 인덱스 안에 m 의 숫자들을 넣었으니, 다 합하면 댐
for i in m :
    sum = sum + int(i)

print(sum)