2011번: 암호코드

문제

상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.

• 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.
• 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.
• 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?
• 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
• 상근: 얼마나 많은데?
• 선영: 구해보자!

어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오.

문제 풀이

알고리즘 : 다이나믹 프로그래밍

왜 와이? : 경우의 수를 세고 최적화 위해

설명

1. 입력은 문자열로 받고 for loop 순회를 한다.
2. 현재 인덱스(i) 와 이전 인덱스 (i-1)를 통해 현재 위치에서 26이하인 숫자임을 확인한다.
3. 26이하라면 DP[i] += DP[i-1] + DP[i-2]
   • 두자리 숫자를 쓸 경우와 한자리의 숫자만 쓸경우를 더한다.
4. 26초과라면 DP[i] += DP[i-1]
   • 한자리의 숫자만 사용할 수 있다.

하지만 코드가 옳지 않은 경우 0 을 출력해야한다.

0이 되는 경우

1. 두자리 숫자를 합쳤을 시 26 이상
2. 0이 두번이상 붙어 나올 경우
3. 맨앞에 0 이 나올 경우

또한, 0이 나와도 가능한 경우 0이 아닐 때 사용되는 풀이와 다른 풀이를 적용해야한다.

즉, 한자리 숫자만 쓸 경우는 빼고 생각해야한다.

이렇게 복잡하게 해야하나 싶다. 일단 내 머릿속에 나온거니 정리해본다.

풀이 총정리

1. 문자열로 입력 받아 for loop
2. 현재 인덱스와 이전 인덱스 문자를 조합해 두자리 숫자를 만들어본다.
3. 현재 위치가 0 이거나 이전 위치가 0 이거나 이후 위치가 0 이면 멈출지 말지 본다
4. dp 배열 업데이트

#include <iostream>
#include <string>
using namespace std;

typedef long long ll;

int N;

ll dp[5010];
int main (){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string str;
    cin >> str;
    dp[0] = 1;
    dp[1] = 1;

    //맨앞자리가 0이면 종료
    if(str[0] == '0'){
        cout << 0;
        return 0;
    }

    for(int i = 1;i<str.size();i++){
            //두자리 숫자 만들어보자
        int one = str[i] - '0';
        int ten = str[i-1] -'0';
        int number = ten * 10 + one;

                //현재 인덱스가 0이라면?
        if(str[i] == '0'){
                //0이어도 26안넘으면 오케이, 하지만 00 이면 탈락
            if(number > 26 || number == 0){
                cout << 0;
                return 0;
            }else{
                    //dp 이월
                dp[i+1] = dp[i];
                continue;
            }
            //이전 인덱스가 0이라면?
        }else if(str[i-1] == '0'){
                //dp 이월
            dp[i+1] = dp[i];
            continue;
            //다음 인덱스가 0이라면?
        }else if(i+1 <= str.size() && str[i+1] == '0'){
            dp[i+1] = dp[i];
            continue;
        }

        if(number > 26){
            dp[i+1] =(dp[i+1] + dp[i] )% rest;
        }else{
            dp[i+1] = (dp[i+1] + dp[i] + dp[i-1]) %rest;
        }
    }
    cout << dp[str.size()];
    return 0;
}

나의 코드가 너무 지저분해서 지피티형에게 수정해달라고 할거다

도와줘요 지피티

#include <iostream>
#include <string>
using namespace std;

typedef long long ll;

const int MOD = 1000000;
ll dp[5001];  // 최대 길이 + 1

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string s;
    cin >> s;

    if (s.empty() || s[0] == '0') {  // 비어있거나 0으로 시작하면
        cout << 0;
        return 0;
    }

    dp[0] = 1;  // 초기 조건 설정
    dp[1] = 1;

    for (size_t i = 1; i < s.length(); i++) {
        int current = s[i] - '0';  // 현재 문자를 숫자로 변환
        int prev = s[i-1] - '0';  // 이전 문자를 숫자로 변환
        int number = prev * 10 + current;  // 두 자리 수

        if (current == 0) {  // 현재 숫자가 '0'인 경우
            if (number == 0 || number > 26) {  // "00"이거나 "30", "40"...
                cout << 0;
                return 0;
            }
            dp[i+1] = dp[i-1];  // "10"이나 "20"
        } else {  // '0'이 아닌 경우
            dp[i+1] = dp[i];  // 일단 현재 위치에서 이전 위치를 이어 받음
            if (number <= 26 && prev != 0) {  // "10" ~ "26" 사이의 유효한 두 자리 수
                dp[i+1] = (dp[i+1] + dp[i-1]) % MOD;
            }
        }
    }

    cout << dp[s.length()];
    return 0;
}

다른점

1. 현재위치에서 0인 경우만 판별
2. 0인경우 dp[i+1] = dp[i-1] 을 통해 두자리 숫자 적용

Layout.tsx

import React, {FC} from "react";
import {Stack, Flex, Box, Text, Button} from '@chakra-ui/react';
import { Link } from "react-router-dom";

const Layout: FC = ({children}) =>{
    return( 
    
    <Stack h="100vh">
        <Flex bg="purple.200" p={4} justifyContent="space-around" alignItems="center">
            <Box>
                <Text fontWeight="bold">h662-Animals</Text>
            </Box>
            <Link to="/">
                <Button size="sm" colorScheme="blue">
                    Main
                </Button>
            </Link>
            <Link to="my-animal">
                <Button size="sm" colorScheme="red">
                    My Animal
                </Button>
            </Link>
            <Link to="sale-animal">
                <Button size="sm" colorScheme="green">
                    Sale Animal
                </Button>
            </Link>
        </Flex>
        <Flex direction="column" h="full" justifyContent="center" alignItems="center">
            {children}
        </Flex>
    </Stack>
    );
}

export default Layout

MyAnimalCard.tsx

import React , {FC, useState, ChangeEvent} from "react";
import {Box, Text, InputGroup, Input, InputRightAddon, Button} from "@chakra-ui/react"
import AnimalCard from "./AnimalCard";
import { saleAnimalTokenContract, web3 } from "../contracts";

export interface IMyanimalCard{
    animalTokenId : string;
    animalType : string;
    animalPrice : string;
}

interface MyAnimalCardProps extends IMyanimalCard {
    saleStatus:boolean;
    account:string;
}

const MyAnimalCard: FC<MyAnimalCardProps> = ({animalTokenId, animalType, animalPrice, saleStatus, account}) =>{
    const [sellPrice, setSellPrice] = useState<string>("");
    const [myAnimalPrice, setMyAnimalPrice] = useState<string>(animalPrice)

    const onChangeSellPrice = (e: ChangeEvent<HTMLInputElement>) =>{
        setSellPrice(e.target.value);
    }

    const onClickSell = async () =>{
        try{
            if(!account || !saleStatus) return;

            const response = await saleAnimalTokenContract.methods
            .setForSaleAnimalToken(animalTokenId, web3.utils.toWei(sellPrice, "ether"))
            .send({from:account});

            if(response.status) {
                setMyAnimalPrice(web3.utils.toWei(sellPrice, "ether"));
                console.log(response)
            }
        }catch(err){
            console.log(err);
        }
    }

    return(
        <Box textAlign="center" w={150}>
            <AnimalCard animalType={animalType} /><Box  mt={2}>
                {animalPrice === "0" ? (
                <>
                    <InputGroup>
                        <Input type='number' value={sellPrice} onChange={onChangeSellPrice}/>
                        <InputRightAddon children="Matic" />
                    </InputGroup>
                    <Button size="sm" colorScheme="green" mt={2} onClick={onClickSell}>
                        Sell
                    </Button>
                </>) : <Text d="inline-block">{web3.utils.fromWei(myAnimalPrice)} Matic</Text> }
            </Box>
        </Box>
    )
}

export default MyAnimalCard;

함수 설명

1. onChangeSellPrice = (e: ChangeEvent<HTMLInputElement>)
   • Input 박스 내의 요소가 바뀔때마다 price 를 바꿔준다.
2. onClickSell
   • 토큰을 판매 등록하는 함수

SaleAnimalCard.tsx

import React, {FC, useState, useEffect} from "react";
import AnimalCard from "./AnimalCard";
import {Box, Text, Button} from "@chakra-ui/react"
import { mintAnimalTokenContract, saleAnimalTokenContract, web3 } from "../contracts";

interface SaleAnimalCardProps{
    animalType:string;
    animalPrice:string;
    animalTokenId: string;
    account:string;
    getOnSaleAnimalTokens: () => Promise<void>;
}

const SaleAnimalCard:FC<SaleAnimalCardProps> =({animalType,animalPrice,animalTokenId, account,getOnSaleAnimalTokens}) =>{
    const [isBuyable, setIsBuyable] = useState<boolean>(false);

    const getAnimalTokenOwner = async () => {
        try{
            const response = await mintAnimalTokenContract.methods.ownerOf(animalTokenId).call();
            
            console.log(response)
            console.log(account);
            setIsBuyable(response.toLocaleLowerCase() === account.toLocaleLowerCase())
        } catch(err){
            console.log(err);
        }   
    } 

    const onClickBuy = async () =>{
        try{
            if(!account) return;
            const response = await saleAnimalTokenContract.methods.purchaseAnimalToken(animalTokenId).send({from: account, value:animalPrice});

            if(response.status){
                getOnSaleAnimalTokens();
            }
        } catch(err){
            console.log(err)
        }
    }

    useEffect(() => {
      
        getAnimalTokenOwner();
    }, [])
    

    return(
        <Box textAlign ="center" w={100}>
            <AnimalCard animalType={animalType} />
            <Box>
                <Text d="inline-block">
                    {web3.utils.fromWei(animalPrice)} Matic
                </Text>
                <Button size="sm" colorScheme="green" m={2} disabled={isBuyable} onClick={onClickBuy}>Buy</Button>
            </Box>
        </Box>
    )
}

export default SaleAnimalCard